Skip to Main content Skip to Navigation
Conference papers

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 distance threshold. This paper 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 widely used phylogenetic inference method.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01616499
Contributor : Maxime Crochemore <>
Submitted on : Friday, October 13, 2017 - 5:01:44 PM
Last modification on : Thursday, April 19, 2018 - 2:24:03 PM
Long-term archiving on: : Sunday, January 14, 2018 - 1:57:24 PM

File

WABI_2017_paper_27.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Maxime Crochemore, Alexandre Francisco, Solon Pissis, Cátia Vaz. Towards distance-based phylogenetic inference in average-case linear-time. International Workshop on Algorithms in Bioinformatics, Aug 2017, Boston, MA, United States. ⟨10.4230/LIPIcs.WABI.2017.00⟩. ⟨hal-01616499⟩

Share

Metrics

Record views

50

Files downloads

142