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 metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
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


Publisher files allowed on an open archive




Maxime Crochemore, Alexandre P Francisco, Solon P 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⟩



Record views


Files downloads