title: Constructing level-2 phylogenetic networks from triplets.
abstract: 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.
authors.affiliation: Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch, New Zealand. l.j.j.v.iersel@gmail.com
authors.forename: Leo
authors.initials: L
authors.lastname: van Iersel
authors.forename: Judith
authors.initials: J
authors.lastname: Keijsper
authors.forename: Steven
authors.initials: S
authors.lastname: Kelk
authors.forename: Leen
authors.initials: L
authors.lastname: Stougie
authors.forename: Ferry
authors.initials: F
authors.lastname: Hagen
authors.forename: Teun
authors.initials: T
authors.lastname: Boekhout
mesh_terms: 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