Read-SpaM: Assembly-free and Alignment-free Comparison of Bacterial Genomes with Low Sequencing Coverage

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2019 Dec 18

PMID 31842735

Citations 13

Authors

Anna-Katharina Lau

Svenja Dorrer

Chris-Andre Leimeister

Christoph Bleidorn

Burkhard Morgenstern

Affiliations

Soon will be listed here.

Abstract

Background: In many fields of biomedical research, it is important to estimate phylogenetic distances between taxa based on low-coverage sequencing reads. Major applications are, for example, phylogeny reconstruction, species identification from small sequencing samples, or bacterial strain typing in medical diagnostics.

Results: We adapted our previously developed software program Filtered Spaced-Word Matches (FSWM) for alignment-free phylogeny reconstruction to take unassembled reads as input; we call this implementation Read-SpaM.

Conclusions: Test runs on simulated reads from semi-artificial and real-world bacterial genomes show that our approach can estimate phylogenetic distances with high accuracy, even for large evolutionary distances and for very low sequencing coverage.

Citing Articles

An alignment-free method for phylogeny estimation using maximum likelihood.

Zahin T, Abrar M, Jewel M, Tasnim T, Bayzid M, Rahman A BMC Bioinformatics. 2025; 26(1):77.

PMID: 40055594 PMC: 11887328. DOI: 10.1186/s12859-025-06080-w.

SHARK enables sensitive detection of evolutionary homologs and functional analogs in unalignable and disordered sequences.

Chow C, Ghosh S, Hadarovich A, Toth-Petroczy A Proc Natl Acad Sci U S A. 2024; 121(42):e2401622121.

PMID: 39383002 PMC: 11494347. DOI: 10.1073/pnas.2401622121.

CONSULT-II: accurate taxonomic identification and profiling using locality-sensitive hashing.

Sapci A, Rachtman E, Mirarab S Bioinformatics. 2024; 40(4).

PMID: 38492564 PMC: 10985673. DOI: 10.1093/bioinformatics/btae150.

App-SpaM: phylogenetic placement of short reads without sequence alignment.

Blanke M, Morgenstern B Bioinform Adv. 2023; 1(1):vbab027.

PMID: 36700102 PMC: 9710606. DOI: 10.1093/bioadv/vbab027.

Quantifying the uncertainty of assembly-free genome-wide distance estimates and phylogenetic relationships using subsampling.

Rachtman E, Sarmashghi S, Bafna V, Mirarab S Cell Syst. 2022; 13(10):817-829.e3.

PMID: 36265468 PMC: 9589918. DOI: 10.1016/j.cels.2022.06.007.

References

Berger S, Krompass D, Stamatakis A . Performance, accuracy, and Web server for evolutionary placement of short sequence reads under maximum likelihood. Syst Biol. 2011; 60(3):291-302. PMC: 3078422. DOI: 10.1093/sysbio/syr010. View

Richter S, Schwarz F, Hering L, Boggemann M, Bleidorn C . The Utility of Genome Skimming for Phylogenomic Analyses as Demonstrated for Glycerid Relationships (Annelida, Glyceridae). Genome Biol Evol. 2015; 7(12):3443-62. PMC: 4700955. DOI: 10.1093/gbe/evv224. View

Chiaromonte F, Yap V, Miller W . Scoring pairwise genomic sequence alignments. Pac Symp Biocomput. 2002; :115-26. DOI: 10.1142/9789812799623_0012. 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

Brown D, Truszkowski J . LSHPlace: fast phylogenetic placement using locality-sensitive hashing. Pac Symp Biocomput. 2013; :310-9. View

Li X, Yang Y, Henry R, Rossetto M, Wang Y, Chen S . Plant DNA barcoding: from gene to genome. Biol Rev Camb Philos Soc. 2014; 90(1):157-66. DOI: 10.1111/brv.12104. View

Yi H, Jin L . Co-phylog: an assembly-free phylogenomic approach for closely related organisms. Nucleic Acids Res. 2013; 41(7):e75. PMC: 3627563. DOI: 10.1093/nar/gkt003. View

Reinert G, Chew D, Sun F, Waterman M . Alignment-free sequence comparison (I): statistics and power. J Comput Biol. 2009; 16(12):1615-34. PMC: 2818754. DOI: 10.1089/cmb.2009.0198. View

Ahlgren N, Ren J, Lu Y, Fuhrman J, Sun F . Alignment-free $d_2^*$ oligonucleotide frequency dissimilarity measure improves prediction of hosts from metagenomically-derived viral sequences. Nucleic Acids Res. 2016; 45(1):39-53. PMC: 5224470. DOI: 10.1093/nar/gkw1002. View

10.

Matsen F, Kodner R, Armbrust E . pplacer: linear time maximum-likelihood and Bayesian phylogenetic placement of sequences onto a fixed reference tree. BMC Bioinformatics. 2010; 11:538. PMC: 3098090. DOI: 10.1186/1471-2105-11-538. View

11.

Hahn L, Leimeister C, Ounit R, Lonardi S, Morgenstern B . rasbhari: Optimizing Spaced Seeds for Database Searching, Read Mapping and Alignment-Free Sequence Comparison. PLoS Comput Biol. 2016; 12(10):e1005107. PMC: 5070788. DOI: 10.1371/journal.pcbi.1005107. View

12.

Linard B, Swenson K, Pardi F . Rapid alignment-free phylogenetic identification of metagenomic sequences. Bioinformatics. 2019; 35(18):3303-3312. DOI: 10.1093/bioinformatics/btz068. View

13.

Zielezinski A, Vinga S, Almeida J, Karlowski W . Alignment-free sequence comparison: benefits, applications, and tools. Genome Biol. 2017; 18(1):186. PMC: 5627421. DOI: 10.1186/s13059-017-1319-7. View

14.

Horwege S, Lindner S, Boden M, Hatje K, Kollmar M, Leimeister C . Spaced words and kmacs: fast alignment-free sequence comparison based on inexact word matches. Nucleic Acids Res. 2014; 42(Web Server issue):W7-11. PMC: 4086093. DOI: 10.1093/nar/gku398. View

15.

Linard B, Arribas P, Andujar C, Crampton-Platt A, Vogler A . Lessons from genome skimming of arthropod-preserving ethanol. Mol Ecol Resour. 2016; 16(6):1365-1377. DOI: 10.1111/1755-0998.12539. View

16.

R Denver D, Brown A, Howe D, Peetz A, Zasada I . Genome Skimming: A Rapid Approach to Gaining Diverse Biological Insights into Multicellular Pathogens. PLoS Pathog. 2016; 12(8):e1005713. PMC: 4973915. DOI: 10.1371/journal.ppat.1005713. View

17.

Leimeister C, Schellhorn J, Dorrer S, Gerth M, Bleidorn C, Morgenstern B . Prot-SpaM: fast alignment-free phylogeny reconstruction based on whole-proteome sequences. Gigascience. 2018; 8(3). PMC: 6436989. DOI: 10.1093/gigascience/giy148. View

18.

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

19.

Leimeister C, Morgenstern B . Kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison. Bioinformatics. 2014; 30(14):2000-8. PMC: 4080746. DOI: 10.1093/bioinformatics/btu331. View

20.

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