Phylogenetic trees from large datasets

Schmidt, Heiko A.

タグ情報を表示リリース履歴を表示詳細要約

Phylogenetic trees from large datasets

Schmidt, H. A. (2003). Phylogenetic trees from large datasets. PhD Thesis, Heinrich–Heine–Universität, Düsseldorf.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0010-89E9-E 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0010-89EA-C

資料種別: 学位論文

ファイル

表示: ファイル

非表示: ファイル

:

PhD-Schmidt.pdf (全文テキスト（全般）), 990KB

ファイルのパーマリンク:
-

ファイル名:
PhD-Schmidt.pdf

説明:
-

OA-Status:

閲覧制限:
制限付き (Max Planck Institute for Molecular Genetics, MBMG; )

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
eDoc_access: MPG

CCライセンス:
-

作成者

表示:

非表示:

作成者:
Schmidt, Heiko A.¹, 著者

所属:
1Max Planck Society, ou_persistent13

内容説明

表示:

非表示:

キーワード: -

要旨: This thesis deals with topics from Bioinformatics /Phyloinformatics. It touches the fields algorithmic complexity, molecular phylogenetics, sequence evolution, as well as parallel computing and, thus, is addressed to an interdisciplinary community. Although it is hardly possible to write a completely self-contained thesis, I tried to provide some basic information needed for members of either community to be able to more easily understand the topics discussed. Consequently, some information might be enclosed that seem trivial to, e.g., computer scientists but which biologists are possibly not familiar with and vice versa.

資料詳細

表示:

非表示:

言語: eng - English

日付: 受理: 2003-07-28

出版の状態: 受理 / 印刷中

ページ: 111 pp

出版情報: Düsseldorf : Heinrich–Heine–Universität

目次: 1. Overview 1
1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Organization of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Molecular Phylogenetics: A General Introduction 5
2.1. Biological Sequences and Molecular Evolution . . . . . . . . . . . . . . . 5
2.1.1. Types of Biological Data . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2. Sequence Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.3. Multiple Sequence Alignment . . . . . . . . . . . . . . . . . . . . 7
2.1.4. Modeling Molecular Evolution . . . . . . . . . . . . . . . . . . . . 7
2.2. Phylogenetic Tree Reconstruction . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1. Notation on Phylogenetic Trees . . . . . . . . . . . . . . . . . . . 10
2.2.2. Types of Phylogenetic Methods . . . . . . . . . . . . . . . . . . . 14
2.2.3. Maximum Likelihood on Phylogenetic Trees . . . . . . . . . . . . 14
2.2.4. Complexity of Phylogenetic Analysis . . . . . . . . . . . . . . . . 17
3. The Quartet Puzzling Algorithm 19
3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2. Methods from the TREE-PUZZLE Package . . . . . . . . . . . . . . . . 20
3.2.1. Likelihood Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.2. Quartet Puzzling . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.2.1. ML Step . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2.2. Puzzling Step . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2.3. Consensus Step . . . . . . . . . . . . . . . . . . . . . . . 24
4. Improvement in Complexity of the Puzzling Step of QP 25
4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2. Complexity Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3. Complexity of the Original Puzzling Step . . . . . . . . . . . . . . . . . . 27
4.4. More E cient Puzzling Step Algorithms . . . . . . . . . . . . . . . . . . 29
4.4.1. Split-Based Puzzling Step Algorithm . . . . . . . . . . . . . . . . 29
4.4.2. Recursive Puzzling Step Algorithm . . . . . . . . . . . . . . . . . 31
4.4.2.1. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4.2.2. Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.4.3. Berry’s MRCA-Based Puzzling Step Algorithm . . . . . . . . . . . 36
4.5. Runtime Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5.1. Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.5.2. Benchmark Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5.3. Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.6. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5. Parallelized Quartet Puzzling 43
5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.2. Parameter Estimation for Evolutionary Models . . . . . . . . . . . . . . . 44
5.2.1. Algorithm: Estimating Model Parameters . . . . . . . . . . . . . 44
5.3. Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4. Runtime Analysis of the Sequential TREE-PUZZLE . . . . . . . . . . . . 46
5.4.1. Runtime of the Parameter Estimation . . . . . . . . . . . . . . . . 46
5.4.2. Runtime of the Quartet Puzzling Algorithm . . . . . . . . . . . . 46
5.5. Parallelizing TREE-PUZZLE . . . . . . . . . . . . . . . . . . . . . . . . 47
5.5.1. Parallelizing the Parameter Estimation . . . . . . . . . . . . . . . 47
5.5.2. Parallelizing Quartet Puzzling . . . . . . . . . . . . . . . . . . . . 47
5.6. Scheduling Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.7. E ciency of Parallel TREE-PUZZLE . . . . . . . . . . . . . . . . . . . . 50
5.7.1. Benchmark Datasets and Setup . . . . . . . . . . . . . . . . . . . 50
5.7.2. Results for Parameter Estimation . . . . . . . . . . . . . . . . . . 51
5.7.3. ML Step and Puzzling Step . . . . . . . . . . . . . . . . . . . . . 51
5.7.4. Overall Scaling of Parallel TREE-PUZZLE . . . . . . . . . . . . . 51
5.8. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6. Large ML Trees from Sequences Using Quartets 57
6.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.2. The Modified Quartet Puzzling Algorithm . . . . . . . . . . . . . . . . . 57
6.2.1. The Algorithm ModPUZZLE . . . . . . . . . . . . . . . . . . . 58
6.3. Computational Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.4. Some Practical Measures on the Method . . . . . . . . . . . . . . . . . . 60
6.5. Discussion and Possible Extensions . . . . . . . . . . . . . . . . . . . . . 61
7. Phylogenetic Trees from Multiple Genesets with Missing Data 63
7.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2. Methods to Combine Datasets . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2.1. Low Level Combination: Total Evidence . . . . . . . . . . . . . . 64
7.2.2. High Level Methods . . . . . . . . . . . . . . . . . . . . . . . . . 64
7.2.2.1. Combining Equal-Sized Datasets: Consensus Methods . 64
7.2.2.2. Combining Overlapping Datasets: Supertree Methods . . 66
7.3. Medium Level Combined Phylogenetic Analysis . . . . . . . . . . . . . . 68
7.3.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.3.2. The Combined Quartet Method to Combine Genesets . . . . . . . 70
7.3.2.1. Combining the ML Quartets . . . . . . . . . . . . . . . . 70
7.3.2.2. Computing the Overall Tree . . . . . . . . . . . . . . . . 71
7.3.2.3. Assessing Whether Genesets Can Be Combined . . . . . 71
7.3.2.4. Overlap-Guided Puzzling Step . . . . . . . . . . . . . . . 72
7.3.2.5. Relative Majority Consensus . . . . . . . . . . . . . . . 73
7.4. The Phylogeny of the Grasses . . . . . . . . . . . . . . . . . . . . . . . . 73
7.4.1. The Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.4.2. Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.4.2.1. Low Level Combination . . . . . . . . . . . . . . . . . . 74
7.4.2.2. High Level Combination . . . . . . . . . . . . . . . . . . 74
7.4.2.3. Medium Level Combination . . . . . . . . . . . . . . . . 74
7.4.3. Parameter Estimates from Poaceae Dataset . . . . . . . . . . . . 76
7.4.4. Combinability of the Poaceae Dataset . . . . . . . . . . . . . . . . 77
7.4.5. Reconstructed Poaceae Phylogeny . . . . . . . . . . . . . . . . . . 78
7.4.5.1. Total Evidence Tree . . . . . . . . . . . . . . . . . . . . 78
7.4.5.2. MRP Supertrees . . . . . . . . . . . . . . . . . . . . . . 78
7.4.5.3. MinCut Supertrees . . . . . . . . . . . . . . . . . . . . 82
7.4.5.4. Combined Quartet Tree . . . . . . . . . . . . . . . . . . 82
7.4.6. Other Published Poaceae Phylogenies . . . . . . . . . . . . . . . . 86
7.5. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.5.1. Problems of Dataset-Combining Methods . . . . . . . . . . . . . . 88
7.5.2. Comparison of the Tree Topologies . . . . . . . . . . . . . . . . . 89
7.5.3. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8. Summary 93
A. Variables and Functions 95
B. Abbreviations 98
Bibliography 101
Acknowledgments 111

査読: -

識別子（DOI, ISBNなど）: eDoc: 194884

学位: 博士号 (PhD)

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物