King's College London

Research portal

Towards Distance-Based Phylogenetic Inference in Average-Case Linear-Time

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

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

Original languageEnglish
Title of host publication17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
EditorsRussell Schwartz, Knut Reinert
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Number of pages14
ISBN (Print)978-3-95977-050-7
Publication statusPublished - 3 Aug 2017
Event17th International Workshop on Algorithms in Bioinformatics (WABI 2017) - Boston, United States
Duration: 21 Aug 201723 Aug 2017

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik


Conference17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
CountryUnited States


King's Authors


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.

Download statistics

No data available

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454