A more practical algorithm for the rooted triplet distance

Jesper Andreas Jansson; Ramesh Rajaby

doi:10.1007/978-3-319-21233-3_9

A more practical algorithm for the rooted triplet distance

Jesper Andreas Jansson, Ramesh Rajaby

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

2 Citations (Scopus)

Abstract

The rooted triplet distance is a measure of the dissimilarity of two phylogenetic trees with identical leaf label sets. An algorithm by Brodal et al. [2] that computes it in O(n log n) time, where n is the number of leaf labels, has recently been implemented in the software package tqDist [14]. In this paper, we show that replacing the hierarchical decomposition tree used in Brodal et al.’s algorithm by a centroid paths-based data structure yields an O(n log3 n)-time algorithm that, although slower in theory, is easier to implement and apparently faster in practice. Simulations for values of n up to 1, 000, 000 support our claims experimentally.

Original language	English
Title of host publication	Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings
Publisher	Springer Verlag
Pages	109-125
Number of pages	17
ISBN (Print)	9783319212326
DOIs	https://doi.org/10.1007/978-3-319-21233-3_9
Publication status	Published - 1 Jan 2015
Externally published	Yes
Event	2nd International Conference on Algorithms for Computational Biology, AlCoB 2015 - Mexico City, Mexico Duration: 4 Aug 2015 → 5 Aug 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9199
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Conference on Algorithms for Computational Biology, AlCoB 2015
Country/Territory	Mexico
City	Mexico City
Period	4/08/15 → 5/08/15

Keywords

Bioinformatics
Centroid path decomposition tree
Phylogenetic tree comparison
Rooted triplet distance

ASJC Scopus subject areas

General Computer Science
Theoretical Computer Science

More information

10.1007/978-3-319-21233-3_9

Cite this

Jansson, J. A., & Rajaby, R. (2015). A more practical algorithm for the rooted triplet distance. In Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings (pp. 109-125). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9199). Springer Verlag. https://doi.org/10.1007/978-3-319-21233-3_9

@inproceedings{6e2cb82c20ae4c68beca102eec3753d1,

title = "A more practical algorithm for the rooted triplet distance",

abstract = "The rooted triplet distance is a measure of the dissimilarity of two phylogenetic trees with identical leaf label sets. An algorithm by Brodal et al. [2] that computes it in O(n log n) time, where n is the number of leaf labels, has recently been implemented in the software package tqDist [14]. In this paper, we show that replacing the hierarchical decomposition tree used in Brodal et al.{\textquoteright}s algorithm by a centroid paths-based data structure yields an O(n log3 n)-time algorithm that, although slower in theory, is easier to implement and apparently faster in practice. Simulations for values of n up to 1, 000, 000 support our claims experimentally.",

keywords = "Bioinformatics, Centroid path decomposition tree, Phylogenetic tree comparison, Rooted triplet distance",

author = "Jansson, {Jesper Andreas} and Ramesh Rajaby",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-21233-3_9",

language = "English",

isbn = "9783319212326",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "109--125",

booktitle = "Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings",

address = "Germany",

note = "2nd International Conference on Algorithms for Computational Biology, AlCoB 2015 ; Conference date: 04-08-2015 Through 05-08-2015",

}

Jansson, JA & Rajaby, R 2015, A more practical algorithm for the rooted triplet distance. in Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9199, Springer Verlag, pp. 109-125, 2nd International Conference on Algorithms for Computational Biology, AlCoB 2015, Mexico City, Mexico, 4/08/15. https://doi.org/10.1007/978-3-319-21233-3_9

A more practical algorithm for the rooted triplet distance. / Jansson, Jesper Andreas; Rajaby, Ramesh.
Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings. Springer Verlag, 2015. p. 109-125 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9199).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - A more practical algorithm for the rooted triplet distance

AU - Jansson, Jesper Andreas

AU - Rajaby, Ramesh

PY - 2015/1/1

Y1 - 2015/1/1

N2 - The rooted triplet distance is a measure of the dissimilarity of two phylogenetic trees with identical leaf label sets. An algorithm by Brodal et al. [2] that computes it in O(n log n) time, where n is the number of leaf labels, has recently been implemented in the software package tqDist [14]. In this paper, we show that replacing the hierarchical decomposition tree used in Brodal et al.’s algorithm by a centroid paths-based data structure yields an O(n log3 n)-time algorithm that, although slower in theory, is easier to implement and apparently faster in practice. Simulations for values of n up to 1, 000, 000 support our claims experimentally.

AB - The rooted triplet distance is a measure of the dissimilarity of two phylogenetic trees with identical leaf label sets. An algorithm by Brodal et al. [2] that computes it in O(n log n) time, where n is the number of leaf labels, has recently been implemented in the software package tqDist [14]. In this paper, we show that replacing the hierarchical decomposition tree used in Brodal et al.’s algorithm by a centroid paths-based data structure yields an O(n log3 n)-time algorithm that, although slower in theory, is easier to implement and apparently faster in practice. Simulations for values of n up to 1, 000, 000 support our claims experimentally.

KW - Bioinformatics

KW - Centroid path decomposition tree

KW - Phylogenetic tree comparison

KW - Rooted triplet distance

UR - http://www.scopus.com/inward/record.url?scp=84951026220&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-21233-3_9

DO - 10.1007/978-3-319-21233-3_9

M3 - Conference article published in proceeding or book

SN - 9783319212326

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 109

EP - 125

BT - Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings

PB - Springer Verlag

T2 - 2nd International Conference on Algorithms for Computational Biology, AlCoB 2015

Y2 - 4 August 2015 through 5 August 2015

ER -

Jansson JA, Rajaby R. A more practical algorithm for the rooted triplet distance. In Algorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings. Springer Verlag. 2015. p. 109-125. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-21233-3_9

A more practical algorithm for the rooted triplet distance

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this