DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2016.12

Fast Compatibility Testing for Rooted Phylogenetic Trees

Authors: Yun Deng and David Fernández-Baca

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract

We consider the following basic problem in phylogenetic tree construction. Let $\mathcal P = {T_1, ..., T_k} be a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility problem asks whether there is a tree T with the following property: for each i in {1, ..., k}, T_i can be obtained from the restriction of T to the species set of T_i by contracting zero or more edges. If such a tree T exists, we say that P is compatible. We give a ~O(M_P) algorithm for the tree compatibility problem, where M_P is the total number of nodes and edges in P. Unlike previous algorithms for this problem, the running time of our method does not depend on the degrees of the nodes in the input trees. Thus, it is equally fast on highly resolved and highly unresolved trees.

Cite as

Yun Deng and David Fernández-Baca. Fast Compatibility Testing for Rooted Phylogenetic Trees. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.CPM.2016.12,
  author =	{Deng, Yun and Fern\'{a}ndez-Baca, David},
  title =	{{Fast Compatibility Testing for Rooted Phylogenetic Trees}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.12},
  URN =		{urn:nbn:de:0030-drops-60884},
  doi =		{10.4230/LIPIcs.CPM.2016.12},
  annote =	{Keywords: Algorithms, computational biology, phylogenetics}
}

Search Results

Documents authored by Deng, Yun

Fast Compatibility Testing for Rooted Phylogenetic Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message