Constructing level-2 phylogenetic networks from triplets.
Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so, to construct such a network [24]. Here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also implemented the algorithm and applied it to yeast data.
van Iersel
Leo
L
Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch, New Zealand. l.j.j.v.iersel@gmail.com
Keijsper
Judith
J
Kelk
Steven
S
Stougie
Leen
L
Hagen
Ferry
F
Boekhout
Teun
T
D000465:Algorithms; D001499:Bayes Theorem; D005075:Biological Evolution; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D016013:Likelihood Functions; D015233:Models, Statistical; D010802:Phylogeny; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D012984:Software; D013997:Time Factors