On the Transformation of MinHash-based Uncorrected Distances into Proper Evolutionary Distances for Phylogenetic Inference

Overview

Journal F1000Res

Specialties Biomedical Engineering
Science

Date 2020 Dec 18

PMID 33335719

Citations 11

Authors

Alexis Criscuolo

Affiliations

Soon will be listed here.

Abstract

Recently developed MinHash-based techniques were proven successful in quickly estimating the level of similarity between large nucleotide sequences. This article discusses their usage and limitations in practice to approximating uncorrected distances between genomes, and transforming these pairwise dissimilarities into proper evolutionary distances. It is notably shown that complex distance measures can be easily approximated using simple transformation formulae based on few parameters. MinHash-based techniques can therefore be very useful for implementing fast yet accurate alignment-free phylogenetic reconstruction procedures from large sets of genomes. This last point of view is assessed with a simulation study using a dedicated bioinformatics tool.

Citing Articles

Multiple introductions of NRCS-A to the neonatal intensive care unit drive neonatal bloodstream infections: a case-control and environmental genomic survey.

Lees E, Gentry J, Webster H, Sanderson N, Eyre D, Wilson D Microb Genom. 2025; 11(1.

PMID: 39773387 PMC: 11706212. DOI: 10.1099/mgen.0.001340.

Description of Cohnella rhizoplanae sp. nov., isolated from the root surface of soybean (Glycine max).

Kampfer P, Glaeser S, McInroy J, Busse H, Clermont D, Criscuolo A Antonie Van Leeuwenhoek. 2024; 118(2):41.

PMID: 39718652 PMC: 11668882. DOI: 10.1007/s10482-024-02051-y.

Rathayibacter tanaceti sp. nov., a Novel Actinobacterium from Tanacetum vulgare Infested by Foliar Nematode Aphelenchoides sp.

Starodumova I, Dorofeeva L, Prisyazhnaya N, Tarlachkov S, Vasilenko O, Avtukh A Curr Microbiol. 2024; 81(5):123.

PMID: 38538917 DOI: 10.1007/s00284-024-03643-7.

Mottle: Accurate pairwise substitution distance at high divergence through the exploitation of short-read mappers and gradient descent.

Prusokiene A, Boonham N, Fox A, Howard T PLoS One. 2024; 19(3):e0298834.

PMID: 38512939 PMC: 10956839. DOI: 10.1371/journal.pone.0298834.

10.1.1, a Producer of Antimicrobial Agents.

Kudryakova I, Afoshin A, Tarlachkov S, Leontyevskaya E, Suzina N, Leontyevskaya Vasilyeva N Microorganisms. 2023; 11(12).

PMID: 38137997 PMC: 10745450. DOI: 10.3390/microorganisms11122853.

References

Guindon S, Gascuel O . Efficient biased estimation of evolutionary distances when substitution rates vary across sites. Mol Biol Evol. 2002; 19(4):534-43. DOI: 10.1093/oxfordjournals.molbev.a004109. View

Susko E, Inagaki Y, Roger A . On inconsistency of the neighbor-joining, least squares, and minimum evolution estimation when substitution processes are incorrectly modeled. Mol Biol Evol. 2004; 21(9):1629-42. DOI: 10.1093/molbev/msh159. View

Takahashi K, Nei M . Efficiencies of fast algorithms of phylogenetic inference under the criteria of maximum parsimony, minimum evolution, and maximum likelihood when a large number of sequences are used. Mol Biol Evol. 2000; 17(8):1251-8. DOI: 10.1093/oxfordjournals.molbev.a026408. View

Page A, Cummins C, Hunt M, Wong V, Reuter S, Holden M . Roary: rapid large-scale prokaryote pan genome analysis. Bioinformatics. 2015; 31(22):3691-3. PMC: 4817141. DOI: 10.1093/bioinformatics/btv421. View

Klotzl F, Haubold B . Phylonium: fast estimation of evolutionary distances from large samples of similar genomes. Bioinformatics. 2019; 36(7):2040-2046. PMC: 7141870. DOI: 10.1093/bioinformatics/btz903. View

Rohling S, Linne A, Schellhorn J, Hosseini M, Dencker T, Morgenstern B . The number of k-mer matches between two DNA sequences as a function of k and applications to estimate phylogenetic distances. PLoS One. 2020; 15(2):e0228070. PMC: 7010260. DOI: 10.1371/journal.pone.0228070. View

Rowe W . When the levee breaks: a practical guide to sketching algorithms for processing the flood of genomic data. Genome Biol. 2019; 20(1):199. PMC: 6744645. DOI: 10.1186/s13059-019-1809-x. View

Sarmashghi S, Bohmann K, Gilbert M, Bafna V, Mirarab S . Skmer: assembly-free and alignment-free sample identification using genome skims. Genome Biol. 2019; 20(1):34. PMC: 6374904. DOI: 10.1186/s13059-019-1632-4. View

Mougel C, Thioulouse J, Perriere G, Nesme X . A mathematical method for determining genome divergence and species delineation using AFLP. Int J Syst Evol Microbiol. 2002; 52(Pt 2):573-586. DOI: 10.1099/00207713-52-2-573. View

10.

Nguyen L, Schmidt H, von Haeseler A, Minh B . IQ-TREE: a fast and effective stochastic algorithm for estimating maximum-likelihood phylogenies. Mol Biol Evol. 2014; 32(1):268-74. PMC: 4271533. DOI: 10.1093/molbev/msu300. View

11.

Dazas M, Badell E, Carmi-Leroy A, Criscuolo A, Brisse S . Taxonomic status of Corynebacterium diphtheriae biovar Belfanti and proposal of Corynebacterium belfantii sp. nov. Int J Syst Evol Microbiol. 2018; 68(12):3826-3831. DOI: 10.1099/ijsem.0.003069. View

12.

Fletcher W, Yang Z . INDELible: a flexible simulator of biological sequence evolution. Mol Biol Evol. 2009; 26(8):1879-88. PMC: 2712615. DOI: 10.1093/molbev/msp098. View

13.

Numanagic I, Gokkaya A, Zhang L, Berger B, Alkan C, Hach F . Fast characterization of segmental duplications in genome assemblies. Bioinformatics. 2018; 34(17):i706-i714. PMC: 6129265. DOI: 10.1093/bioinformatics/bty586. View

14.

Leimeister C, Sohrabi-Jahromi S, Morgenstern B . Fast and accurate phylogeny reconstruction using filtered spaced-word matches. Bioinformatics. 2017; 33(7):971-979. PMC: 5409309. DOI: 10.1093/bioinformatics/btw776. View

15.

Felsenstein J . Evolutionary trees from DNA sequences: a maximum likelihood approach. J Mol Evol. 1981; 17(6):368-76. DOI: 10.1007/BF01734359. View

16.

Jain C, Rodriguez-R L, Phillippy A, Konstantinidis K, Aluru S . High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries. Nat Commun. 2018; 9(1):5114. PMC: 6269478. DOI: 10.1038/s41467-018-07641-9. View

17.

Fan H, Ives A, Surget-Groba Y, Cannon C . An assembly and alignment-free method of phylogeny reconstruction from next-generation sequencing data. BMC Genomics. 2015; 16:522. PMC: 4501066. DOI: 10.1186/s12864-015-1647-5. View

18.

Katoh K, Standley D . MAFFT multiple sequence alignment software version 7: improvements in performance and usability. Mol Biol Evol. 2013; 30(4):772-80. PMC: 3603318. DOI: 10.1093/molbev/mst010. View

19.

Tajima F, Nei M . Estimation of evolutionary distance between nucleotide sequences. Mol Biol Evol. 1984; 1(3):269-85. DOI: 10.1093/oxfordjournals.molbev.a040317. View

20.

Tamura K, Kumar S . Evolutionary distance estimation under heterogeneous substitution pattern among lineages. Mol Biol Evol. 2002; 19(10):1727-36. DOI: 10.1093/oxfordjournals.molbev.a003995. View