Phylogeny: Discrete and Random Processes in Evolution

Preface ix
Acknowledgments xi
Commonly Used Symbols xiii
1 Phylogeny 1
1.1 What is phylogenetics? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Phylogenetic trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Basic combinatorics of discrete phylogenies 15
2.1 Counting trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Rooted trees as nested sets of clusters . . . . . . . . . . . . . . . . . . . . . 18
2.3 Refinement, compatibility, and encoding . . . . . . . . . . . . . . . . . . . 21
2.4 Unrooted trees as systems of splits . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Tree rearrangement metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Consensus functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Tree shape and random discrete phylogenies 41
3.1 Tree shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 The shape of evolving trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Measuring and modeling tree shape . . . . . . . . . . . . . . . . . . . . . . 53
3.4 Cherries and extended Pólya urn models . . . . . . . . . . . . . . . . . . . 58
4 Pulling trees apart and putting trees together 63
4.1 Restriction and display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 When is a collection of trees compatible? . . . . . . . . . . . . . . . . . . . 67
4.3 Sets of trees that “define” and “identify” a phylogeny . . . . . . . . . . . 72
4.4 Agreement subtrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 Phylogenetic decisiveness and terraces . . . . . . . . . . . . . . . . . . . . . 82
5 Phylogenies based on discrete characters 87
5.1 Characters, homoplasy, and perfect phylogeny . . . . . . . . . . . . . . . 87
5.2 Minimal evolution (maximum parsimony (MP)) . . . . . . . . . . . . . . 100
5.3 Minimal evolution trees for a sequence of characters . . . . . . . . . . . 107
6 Continuous phylogenies and distance-based tree reconstruction 111
6.1 Metrics from trees with edge lengths. . . . . . . . . . . . . . . . . . . . . . 111
6.2 Distance-based tree reconstruction methods . . . . . . . . . . . . . . . . . 121
6.3 Generalizations and geometry . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.4 Phylogenetic diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7 Evolution on a tree: Part one 147
7.1 Nonhomogeneous Markov chains . . . . . . . . . . . . . . . . . . . . . . . 148
7.2 From Markov chains to processes on trees . . . . . . . . . . . . . . . . . . 153
7.3 Classes and properties of models . . . . . . . . . . . . . . . . . . . . . . . . 157
7.4 The Hadamard story . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.5 Phylogenetic mixture models . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8 Evolution on a tree: Part two 177
8.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.2 Phylogeny reconstruction methods and properties . . . . . . . . . . . . 180
8.3 Algebraic analysis of Markov models . . . . . . . . . . . . . . . . . . . . . 191
8.4 The infinite-state random cluster model . . . . . . . . . . . . . . . . . . . 197
8.5 Additional topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
9 Evolution of trees 205
9.1 Yule pure-birth trees: The simplest model . . . . . . . . . . . . . . . . . . 206
9.2 Birth-death models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
9.3 Gene trees and species trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
10 Introduction to phylogenetic networks 237
10.1 To tree or not to tree: Why networks? . . . . . . . . . . . . . . . . . . . . 237
10.2 Implicit (unrooted) networks . . . . . . . . . . . . . . . . . . . . . . . . . . 238
10.3 Explicit (directed) networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
10.4 Trees displayed by networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
10.5 Reconstructing networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
10.6 Additional topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Bibliography 269
Index 291