Building a Small and Informative Phylogenetic Supertree

Publikation: KonferencebidragKonferenceabstrakt til konferenceForskningpeer review

Standard

Building a Small and Informative Phylogenetic Supertree. / Jansson, Jesper; Mampentzidis, Konstantinos; Thekkumpadan Puthiyaveedu, Sandhya.

2019. Abstract fra Workshop on Algorithms in Bioinformatics (WABI) 2019, Buffalo, New York, USA.

Publikation: KonferencebidragKonferenceabstrakt til konferenceForskningpeer review

Harvard

Jansson, J, Mampentzidis, K & Thekkumpadan Puthiyaveedu, S 2019, 'Building a Small and Informative Phylogenetic Supertree', Workshop on Algorithms in Bioinformatics (WABI) 2019, Buffalo, New York, USA, 08/09/2019 - 10/09/2019.

APA

Jansson, J., Mampentzidis, K., & Thekkumpadan Puthiyaveedu, S. (2019). Building a Small and Informative Phylogenetic Supertree. Abstract fra Workshop on Algorithms in Bioinformatics (WABI) 2019, Buffalo, New York, USA.

CBE

Jansson J, Mampentzidis K, Thekkumpadan Puthiyaveedu S. 2019. Building a Small and Informative Phylogenetic Supertree. Abstract fra Workshop on Algorithms in Bioinformatics (WABI) 2019, Buffalo, New York, USA.

MLA

Jansson, Jesper, Konstantinos Mampentzidis og Sandhya Thekkumpadan Puthiyaveedu Building a Small and Informative Phylogenetic Supertree. Workshop on Algorithms in Bioinformatics (WABI) 2019, 08 sep. 2019, Buffalo, New York, USA, Konferenceabstrakt til konference, 2019.

Vancouver

Jansson J, Mampentzidis K, Thekkumpadan Puthiyaveedu S. Building a Small and Informative Phylogenetic Supertree. 2019. Abstract fra Workshop on Algorithms in Bioinformatics (WABI) 2019, Buffalo, New York, USA.

Author

Jansson, Jesper ; Mampentzidis, Konstantinos ; Thekkumpadan Puthiyaveedu, Sandhya. / Building a Small and Informative Phylogenetic Supertree. Abstract fra Workshop on Algorithms in Bioinformatics (WABI) 2019, Buffalo, New York, USA.

Bibtex

@conference{785c4c382c16429fb8172361a1a81dac,
title = "Building a Small and Informative Phylogenetic Supertree",
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 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 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(qn) 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(nlogn) time complexity [SODA 2013, ESA 2017]) whenever q=o(logn).",
keywords = "phylogenetic tree, supertree, rooted triplet, approximation algorithm",
author = "Jesper Jansson and Konstantinos Mampentzidis and {Thekkumpadan Puthiyaveedu}, Sandhya",
year = "2019",
language = "English",
note = "Workshop on Algorithms in Bioinformatics (WABI) 2019 ; Conference date: 08-09-2019 Through 10-09-2019",
url = "https://acm-bcb.org/WABI/2019/",

}

RIS

TY - ABST

T1 - Building a Small and Informative Phylogenetic Supertree

AU - Jansson, Jesper

AU - Mampentzidis, Konstantinos

AU - Thekkumpadan Puthiyaveedu, Sandhya

PY - 2019

Y1 - 2019

N2 - 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 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 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(qn) 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(nlogn) time complexity [SODA 2013, ESA 2017]) whenever q=o(logn).

AB - 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 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 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(qn) 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(nlogn) time complexity [SODA 2013, ESA 2017]) whenever q=o(logn).

KW - phylogenetic tree

KW - supertree

KW - rooted triplet

KW - approximation algorithm

M3 - Conference abstract for conference

T2 - Workshop on Algorithms in Bioinformatics (WABI) 2019

Y2 - 8 September 2019 through 10 September 2019

ER -