Towards distance-based phylogenetic inference in average-case linear-time

Maxime Crochemore; Alexandre P. Francisco; Solon P. Pissis; Cátia Vaz

doi:10.4230/LIPIcs.WABI.2017.9

Towards distance-based phylogenetic inference in average-case linear-time

Maxime Crochemore, Alexandre P. Francisco, Solon P. Pissis, Cátia Vaz

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Computing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method.

Original language	English
Title of host publication	17th International Workshop on Algorithms in Bioinformatics, WABI 2017
Editors	Knut Reinert, Russell Schwartz
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959770507
DOIs	https://doi.org/10.4230/LIPIcs.WABI.2017.9
Publication status	Published - 1 Aug 2017
Externally published	Yes
Event	17th International Workshop on Algorithms in Bioinformatics, WABI 2017 - Boston, United States Duration: 21 Aug 2017 → 23 Aug 2017

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	88
ISSN (Print)	1868-8969

Conference

Conference	17th International Workshop on Algorithms in Bioinformatics, WABI 2017
Country/Territory	United States
City	Boston
Period	21/08/17 → 23/08/17

Funding

∗ This work was partly supported by the Royal Society International Exchanges Scheme, and by na-tional funds through FCT – Fundação para a Ciência e Tecnologia, under projects BacGenTrack (TUBITACK/0004/2014), PRECISE (SAICTPAC/0021/2015) and UID/CEC/500021/2013.

Funders	Funder number
Royal Society
Instituto Nacional de Ciência e Tecnologia para Excitotoxicidade e Neuroproteção	TUBITACK/0004/2014, SAICTPAC/0021/2015, UID/CEC/500021/2013
Fundació Catalana de Trasplantament

Keywords

Computational biology
Hamming distance
Phylogenetic inference

Access to Document

10.4230/LIPIcs.WABI.2017.9

Persistent URL (handle)

Copy link address

Cite this

Crochemore, M., Francisco, A. P., Pissis, S. P., & Vaz, C. (2017). Towards distance-based phylogenetic inference in average-case linear-time. In K. Reinert, & R. Schwartz (Eds.), 17th International Workshop on Algorithms in Bioinformatics, WABI 2017 Article 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 88). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.WABI.2017.9

Crochemore, Maxime ; Francisco, Alexandre P. ; Pissis, Solon P. et al. / Towards distance-based phylogenetic inference in average-case linear-time. 17th International Workshop on Algorithms in Bioinformatics, WABI 2017. editor / Knut Reinert ; Russell Schwartz. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{093cf8d5f9c642868fc448e6cdc42257,

title = "Towards distance-based phylogenetic inference in average-case linear-time",

abstract = "Computing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method.",

keywords = "Computational biology, Hamming distance, Phylogenetic inference",

author = "Maxime Crochemore and Francisco, {Alexandre P.} and Pissis, {Solon P.} and C{\'a}tia Vaz",

year = "2017",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.WABI.2017.9",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Knut Reinert and Russell Schwartz",

booktitle = "17th International Workshop on Algorithms in Bioinformatics, WABI 2017",

note = "17th International Workshop on Algorithms in Bioinformatics, WABI 2017 ; Conference date: 21-08-2017 Through 23-08-2017",

}

Crochemore, M, Francisco, AP, Pissis, SP & Vaz, C 2017, Towards distance-based phylogenetic inference in average-case linear-time. in K Reinert & R Schwartz (eds), 17th International Workshop on Algorithms in Bioinformatics, WABI 2017., 9, Leibniz International Proceedings in Informatics, LIPIcs, vol. 88, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 17th International Workshop on Algorithms in Bioinformatics, WABI 2017, Boston, United States, 21/08/17. https://doi.org/10.4230/LIPIcs.WABI.2017.9

Towards distance-based phylogenetic inference in average-case linear-time. / Crochemore, Maxime; Francisco, Alexandre P.; Pissis, Solon P. et al.
17th International Workshop on Algorithms in Bioinformatics, WABI 2017. ed. / Knut Reinert; Russell Schwartz. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 88).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Towards distance-based phylogenetic inference in average-case linear-time

AU - Crochemore, Maxime

AU - Francisco, Alexandre P.

AU - Pissis, Solon P.

AU - Vaz, Cátia

PY - 2017/8/1

Y1 - 2017/8/1

N2 - Computing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method.

AB - Computing genetic evolution distances among a set of taxa dominates the running time of many phylogenetic inference methods. Most of genetic evolution distance definitions rely, even if indirectly, on computing the pairwise Hamming distance among sequences or profiles. We propose here an average-case linear-time algorithm to compute pairwise Hamming distances among a set of taxa under a given Hamming distance threshold. This article includes both a theoretical analysis and extensive experimental results concerning the proposed algorithm. We further show how this algorithm can be successfully integrated into a well known phylogenetic inference method.

KW - Computational biology

KW - Hamming distance

KW - Phylogenetic inference

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

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

U2 - 10.4230/LIPIcs.WABI.2017.9

DO - 10.4230/LIPIcs.WABI.2017.9

M3 - Conference contribution

AN - SCOPUS:85028761193

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 17th International Workshop on Algorithms in Bioinformatics, WABI 2017

A2 - Reinert, Knut

A2 - Schwartz, Russell

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 17th International Workshop on Algorithms in Bioinformatics, WABI 2017

Y2 - 21 August 2017 through 23 August 2017

ER -

Crochemore M, Francisco AP, Pissis SP, Vaz C. Towards distance-based phylogenetic inference in average-case linear-time. In Reinert K, Schwartz R, editors, 17th International Workshop on Algorithms in Bioinformatics, WABI 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. 9. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.WABI.2017.9

Towards distance-based phylogenetic inference in average-case linear-time

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this