Alignment-free Genomic Sequence Comparison Using FCGR and Signal Processing

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2020 Jan 1

PMID 31888438

Citations 14

Authors

Daniel Lichtblau

Affiliations

Soon will be listed here.

Abstract

Background: Alignment-free methods of genomic comparison offer the possibility of scaling to large data sets of nucleotide sequences comprised of several thousand or more base pairs. Such methods can be used for purposes of deducing "nearby" species in a reference data set, or for constructing phylogenetic trees.

Results: We describe one such method that gives quite strong results. We use the Frequency Chaos Game Representation (FCGR) to create images from such sequences, We then reduce dimension, first using a Fourier trig transform, followed by a Singular Values Decomposition (SVD). This gives vectors of modest length. These in turn are used for fast sequence lookup, construction of phylogenetic trees, and classification of virus genomic data. We illustrate the accuracy and scalability of this approach on several benchmark test sets.

Conclusions: The tandem of FCGR and dimension reductions using Fourier-type transforms and SVD provides a powerful approach for alignment-free genomic comparison. Results compare favorably and often surpass best results reported in prior literature. Good scalability is also observed.

Citing Articles

Overview and Prospects of DNA Sequence Visualization.

Wu Y, Xie X, Zhu J, Guan L, Li M Int J Mol Sci. 2025; 26(2).

PMID: 39859192 PMC: 11764684. DOI: 10.3390/ijms26020477.

CGRclust: Chaos Game Representation for twin contrastive clustering of unlabelled DNA sequences.

Alipour F, Hill K, Kari L BMC Genomics. 2024; 25(1):1214.

PMID: 39695938 PMC: 11657719. DOI: 10.1186/s12864-024-11135-y.

Exploring geometry of genome space via Grassmann manifolds.

Li X, Zhou T, Feng X, Yau S, Yau S Innovation (Camb). 2024; 5(5):100677.

PMID: 39206218 PMC: 11350263. DOI: 10.1016/j.xinn.2024.100677.

PC-mer: An Ultra-fast memory-efficient tool for metagenomics profiling and classification.

Akbari Rokn Abadi S, Mohammadi A, Koohi S PLoS One. 2024; 19(8):e0307279.

PMID: 39088438 PMC: 11293629. DOI: 10.1371/journal.pone.0307279.

Genome analysis through image processing with deep learning models.

Zhang Y, Imoto S J Hum Genet. 2024; 69(10):519-525.

PMID: 39085457 PMC: 11422167. DOI: 10.1038/s10038-024-01275-0.

References

Pei S, Dong R, He R, Yau S . Large-Scale Genome Comparison Based on Cumulative Fourier Power and Phase Spectra: Central Moment and Covariance Vector. Comput Struct Biotechnol J. 2019; 17:982-994. PMC: 6661692. DOI: 10.1016/j.csbj.2019.07.003. View

Kubicova V, Provaznik I . Use of whole genome DNA spectrograms in bacterial classification. Comput Biol Med. 2015; 69:298-307. DOI: 10.1016/j.compbiomed.2015.04.038. View

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

Jeffrey H . Chaos game representation of gene structure. Nucleic Acids Res. 1990; 18(8):2163-70. PMC: 330698. DOI: 10.1093/nar/18.8.2163. View

Sievers F, Wilm A, Dineen D, Gibson T, Karplus K, Li W . Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega. Mol Syst Biol. 2011; 7:539. PMC: 3261699. DOI: 10.1038/msb.2011.75. View

Berger B, Peng J, Singh M . Computational solutions for omics data. Nat Rev Genet. 2013; 14(5):333-46. PMC: 3966295. DOI: 10.1038/nrg3433. View

Xie G, Mo Z . Three 3D graphical representations of DNA primary sequences based on the classifications of DNA bases and their applications. J Theor Biol. 2010; 269(1):123-30. PMC: 7126940. DOI: 10.1016/j.jtbi.2010.10.018. View

Karamichalis R, Kari L, Konstantinidis S, Kopecki S, Solis-Reyes S . Additive methods for genomic signatures. BMC Bioinformatics. 2016; 17(1):313. PMC: 4994249. DOI: 10.1186/s12859-016-1157-8. View

Edwards R, McNair K, Faust K, Raes J, Dutilh B . Computational approaches to predict bacteriophage-host relationships. FEMS Microbiol Rev. 2015; 40(2):258-72. PMC: 5831537. DOI: 10.1093/femsre/fuv048. View

10.

Benson D, Cavanaugh M, Clark K, Karsch-Mizrachi I, Lipman D, Ostell J . GenBank. Nucleic Acids Res. 2016; 45(D1):D37-D42. PMC: 5210553. DOI: 10.1093/nar/gkw1070. View

11.

Hamori E, Ruskin J . H curves, a novel method of representation of nucleotide series especially suited for long DNA sequences. J Biol Chem. 1983; 258(2):1318-27. View

12.

Pei S, Dong W, Chen X, He R, Yau S . Fast and accurate genome comparison using genome images: The Extended Natural Vector Method. Mol Phylogenet Evol. 2019; 141:106633. DOI: 10.1016/j.ympev.2019.106633. View

13.

Anastassiou D . Frequency-domain analysis of biomolecular sequences. Bioinformatics. 2001; 16(12):1073-81. DOI: 10.1093/bioinformatics/16.12.1073. View

14.

Almeida J, Carrico J, Maretzek A, Noble P, Fletcher M . Analysis of genomic sequences by Chaos Game Representation. Bioinformatics. 2001; 17(5):429-37. DOI: 10.1093/bioinformatics/17.5.429. View

15.

Haubold B . Alignment-free phylogenetics and population genetics. Brief Bioinform. 2013; 15(3):407-18. DOI: 10.1093/bib/bbt083. View

16.

Joseph J, Sasikumar R . Chaos game representation for comparison of whole genomes. BMC Bioinformatics. 2006; 7:243. PMC: 1482720. DOI: 10.1186/1471-2105-7-243. View

17.

Kuksa P, Pavlovic V . Efficient alignment-free DNA barcode analytics. BMC Bioinformatics. 2009; 10 Suppl 14:S9. PMC: 2775155. DOI: 10.1186/1471-2105-10-S14-S9. View

18.

Loh P, Baym M, Berger B . Compressive genomics. Nat Biotechnol. 2012; 30(7):627-30. DOI: 10.1038/nbt.2241. View

19.

Farkas T, Sitarcik J, Brejova B, Lucka M . SWSPM: A Novel Alignment-Free DNA Comparison Method Based on Signal Processing Approaches. Evol Bioinform Online. 2019; 15:1176934319849071. PMC: 6545658. DOI: 10.1177/1176934319849071. View

20.

Mendizabal-Ruiz G, Roman-Godinez I, Torres-Ramos S, Salido-Ruiz R, Morales J . On DNA numerical representations for genomic similarity computation. PLoS One. 2017; 12(3):e0173288. PMC: 5360225. DOI: 10.1371/journal.pone.0173288. View