1 Search Results for "T. P., Sandhya"

Document

DOI: 10.4230/LIPIcs.WABI.2019.1

Building a Small and Informative Phylogenetic Supertree

Authors: Jesper Jansson, Konstantinos Mampentzidis, and Sandhya T. P.

Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)

Abstract

We combine two fundamental, previously studied optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency (MAXRTC) and minimally resolved supertree (MINRS) into a new problem, which we call q-maximum rooted triplets consistency (q-MAXRTC). The input to our new problem is a set R of resolved triplets (rooted, binary phylogenetic trees with three leaves each) and the objective is to find a phylogenetic tree with exactly q internal nodes that contains the largest possible number of triplets from R. We first prove that q-MAXRTC is NP-hard even to approximate within a constant ratio for every fixed q >= 2, and then develop various polynomial-time approximation algorithms for different values of q. Next, we show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much triplet branching information. As an extreme example, we show that allowing only nine internal nodes is still sufficient to capture on average 80% of the rooted triplets from some recently published trees, each having between 760 and 3081 internal nodes. Finally, to demonstrate the algorithmic advantage of using trees with few internal nodes, we propose a new algorithm for computing the rooted triplet distance between two phylogenetic trees over a leaf label set of size n that runs in O(q n) time, where q is the number of internal nodes in the smaller tree, and is therefore faster than the currently best algorithms for the problem (with O(n log n) time complexity [SODA 2013, ESA 2017]) whenever q = o(log n).

Cite as

Jesper Jansson, Konstantinos Mampentzidis, and Sandhya T. P.. Building a Small and Informative Phylogenetic Supertree. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansson_et_al:LIPIcs.WABI.2019.1,
  author =	{Jansson, Jesper and Mampentzidis, Konstantinos and T. P., Sandhya},
  title =	{{Building a Small and Informative Phylogenetic Supertree}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Huber, Katharina T. and Gusfield, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.1},
  URN =		{urn:nbn:de:0030-drops-110316},
  doi =		{10.4230/LIPIcs.WABI.2019.1},
  annote =	{Keywords: phylogenetic tree, supertree, rooted triplet, approximation algorithm}
}

Refine by Author
1 Jansson, Jesper
1 Mampentzidis, Konstantinos
1 T. P., Sandhya

Refine by Classification
1 Mathematics of computing → Trees

Refine by Keyword
1 approximation algorithm
1 phylogenetic tree
1 rooted triplet
1 supertree

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "T. P., Sandhya"

Building a Small and Informative Phylogenetic Supertree

Abstract

Cite as

Thanks for your feedback!

Could not send message