Research output: Scientific - peer-review › Article

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.

Original language | English |
---|---|

Pages | 667-681 |

Journal | IEEE/ACM Transactions on Computational Biology and Bioinformatics |

Journal publication date | 2009 |

Volume | 6 |

Issue | 4 |

DOI | |

State | Published |

Peer-reviewed | Yes |

ID: 151357