Basic Phylogenetic Combinatorics

by Andreas Dress , Katharina T. Huber , Jacobus Koolen , Vincent Moulton , Andreas Spillner

• ISBN13: 9780521768320
• ISBN10: 0521768322
• Format: Hardcover
• Copyright: 2012-01-16
• Publisher: Cambridge University Press

Summary

Phylogenetic combinatorics is a branch of discrete applied mathematics concerned with the combinatorial description and analysis of phylogenetic trees and related mathematical structures such as phylogenetic networks and tight spans. Based on a natural conceptual framework, the book focuses on the interrelationship between the principal options for encoding phylogenetic trees: split systems, quartet systems and metrics. Such encodings provide useful options for analyzing and manipulating phylogenetic trees and networks, and are at the basis of much of phylogenetic data processing. This book highlights how each one provides a unique perspective for viewing and perceiving the combinatorial structure of a phylogenetic tree and is, simultaneously, a rich source for combinatorial analysis and theory building. Graduate students and researchers in mathematics and computer science will enjoy exploring this fascinating new area and learn how mathematics may be used to help solve topical problems arising in evolutionary biology.

Table of Contents

Preface	p. ix
Preliminaries	p. 1
Sets, set systems, and partially ordered sets	p. 1
Graphs	p. 4
Metric spaces	p. 13
Computational complexity	p. 19
Encoding X-trees	p. 21
X-trees	p. 21
Encoding X-trees with splits	p. 23
Encoding X-trees with metrics	p. 26
Encoding X-trees with quartets	p. 27
Consistency of X-tree encodings	p. 31
The 4-point condition	p. 31
Compatibility	p. 38
Quartet systems	p. 42
From split systems to networks	p. 50
The Buneman graph	p. 51
The Buneman graph of a compatible split system	p. 59
Median networks	p. 63
Split networks	p. 65
Split graphs and metrics: The theory of X-nets	p. 72
From metrics to networks: The tight span	p. 75
The tight span	p. 75
A canonical contraction from P(D) onto T(D)	p. 82
The tight span of a finite metric space	p. 87
Networks from tight spans	p. 93
Network realizations of metrics	p. 97
Optimal and hereditarily optimal realizations	p. 100
From quartet and tree systems to trees	p. 104
On quartet systems	p. 105
On set and tree systems	p. 113
Constructing trees from quartet, tree, and set systems	p. 118
Slim tree systems	p. 121
Definitive set systems	p. 128
From metrics to split systems and back	p. 137
Buneman splits	p. 137
Weakly compatible split systems	p. 146
From weighted split systems to bivariate maps	p. 161
The Buneman complex and the tight span	p. 167
Maps to and from quartet systems	p. 171
A Galois connection between split and quartet systems	p. 171
A map from quartets to metrics	p. 177
Transitive quartet systems	p. 180
Rooted trees and the Farris transform	p. 195
Rooted X-trees, clusters, and triplets	p. 198
Dated rooted X-trees and hierarchical dissimilarities	p. 202
Affine versus projective clustering and the combinatorial Farris transform	p. 205
Hierarchical dissimilarities, hyperbolic maps, and their Farris transform	p. 209
Hierarchical dissimilarities, generalized metrics, and the tight-span construction	p. 214
Algorithmic issues	p. 218
On measuring and removing inconsistencies	p. 222
k-compatibility	p. 222
A-hierarchical approximations	p. 230
Quartet-Joining and QNet	p. 236
Commonly used symbols	p. 242
Bibliography	p. 253
Index	p. 261
Table of Contents provided by Ingram. All Rights Reserved.