GRAMEP: an Alignment-free Method Based on the Maximum Entropy Principle for Identifying SNPs

Overview

Journal BMC Bioinformatics

Publisher Biomed Central

Specialty Biology

Date 2025 Feb 25

PMID 40000933

Authors

Matheus Henrique Pimenta-Zanon

Andre Yoshiaki Kashiwabara

Andre Luis Laforga Vanzela

Fabricio Martins Lopes

Affiliations

Soon will be listed here.

Abstract

Background: Advances in high throughput sequencing technologies provide a huge number of genomes to be analyzed. Thus, computational methods play a crucial role in analyzing and extracting knowledge from the data generated. Investigating genomic mutations is critical because of their impact on chromosomal evolution, genetic disorders, and diseases. It is common to adopt aligning sequences for analyzing genomic variations. However, this approach can be computationally expensive and restrictive in scenarios with large datasets.

Results: We present a novel method for identifying single nucleotide polymorphisms (SNPs) in DNA sequences from assembled genomes. This study proposes GRAMEP, an alignment-free approach that adopts the principle of maximum entropy to discover the most informative k-mers specific to a genome or set of sequences under investigation. The informative k-mers enable the detection of variant-specific mutations in comparison to a reference genome or other set of sequences. In addition, our method offers the possibility of classifying novel sequences with no need for organism-specific information. GRAMEP demonstrated high accuracy in both in silico simulations and analyses of viral genomes, including Dengue, HIV, and SARS-CoV-2. Our approach maintained accurate SARS-CoV-2 variant identification while demonstrating a lower computational cost compared to methods with the same purpose.

Conclusions: GRAMEP is an open and user-friendly software based on maximum entropy that provides an efficient alignment-free approach to identifying and classifying unique genomic subsequences and SNPs with high accuracy, offering advantages over comparative methods. The instructions for use, applicability, and usability of GRAMEP are open access at https://github.com/omatheuspimenta/GRAMEP .

References

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

Garg S . Computational methods for chromosome-scale haplotype reconstruction. Genome Biol. 2021; 22(1):101. PMC: 8040228. DOI: 10.1186/s13059-021-02328-9. View

Crick F . Central dogma of molecular biology. Nature. 1970; 227(5258):561-3. DOI: 10.1038/227561a0. View

Khare S, Gurry C, Freitas L, Schultz M, Bach G, Diallo A . GISAID's Role in Pandemic Response. China CDC Wkly. 2021; 3(49):1049-1051. PMC: 8668406. DOI: 10.46234/ccdcw2021.255. View

Janzakova K, Balafrej I, Kumar A, Garg N, Scholaert C, Rouat J . Structural plasticity for neuromorphic networks with electropolymerized dendritic PEDOT connections. Nat Commun. 2023; 14(1):8143. PMC: 10709651. DOI: 10.1038/s41467-023-43887-8. View

Worobey M . Dissecting the early COVID-19 cases in Wuhan. Science. 2021; 374(6572):1202-1204. DOI: 10.1126/science.abm4454. View

Chen J, Li F, Tian J, Xie X, Tang Q, Chen Y . Varicella zoster virus reactivation following COVID-19 vaccination in patients with autoimmune inflammatory rheumatic diseases: A cross-sectional Chinese study of 318 cases. J Med Virol. 2022; 95(1):e28307. PMC: 9878204. DOI: 10.1002/jmv.28307. View

Olson R, Assaf R, Brettin T, Conrad N, Cucinell C, Davis J . Introducing the Bacterial and Viral Bioinformatics Resource Center (BV-BRC): a resource combining PATRIC, IRD and ViPR. Nucleic Acids Res. 2022; 51(D1):D678-D689. PMC: 9825582. DOI: 10.1093/nar/gkac1003. View

Plummer E, Buck M, Sanchez M, Greenbaum J, Turner J, Grewal R . Dengue Virus Evolution under a Host-Targeted Antiviral. J Virol. 2015; 89(10):5592-601. PMC: 4442503. DOI: 10.1128/JVI.00028-15. View

Smith T, Waterman M . Identification of common molecular subsequences. J Mol Biol. 1981; 147(1):195-7. DOI: 10.1016/0022-2836(81)90087-5. View

Solis-Reyes S, Avino M, Poon A, Kari L . An open-source k-mer based machine learning tool for fast and accurate subtyping of HIV-1 genomes. PLoS One. 2018; 13(11):e0206409. PMC: 6235296. DOI: 10.1371/journal.pone.0206409. View

10.

Garg S . Towards routine chromosome-scale haplotype-resolved reconstruction in cancer genomics. Nat Commun. 2023; 14(1):1358. PMC: 10011606. DOI: 10.1038/s41467-023-36689-5. View

11.

Barros-Carvalho G, Van Sluys M, Lopes F . An Efficient Approach to Explore and Discriminate Anomalous Regions in Bacterial Genomes Based on Maximum Entropy. J Comput Biol. 2017; 24(11):1125-1133. DOI: 10.1089/cmb.2017.0042. View

12.

Song N, Joseph J, Davis G, Durand D . Sequence similarity network reveals common ancestry of multidomain proteins. PLoS Comput Biol. 2008; 4(4):e1000063. PMC: 2377100. DOI: 10.1371/journal.pcbi.1000063. View

13.

Harvey W, Carabelli A, Jackson B, Gupta R, Thomson E, Harrison E . SARS-CoV-2 variants, spike mutations and immune escape. Nat Rev Microbiol. 2021; 19(7):409-424. PMC: 8167834. DOI: 10.1038/s41579-021-00573-0. View

14.

Andersen K, Rambaut A, Lipkin W, Holmes E, Garry R . The proximal origin of SARS-CoV-2. Nat Med. 2020; 26(4):450-452. PMC: 7095063. DOI: 10.1038/s41591-020-0820-9. View

15.

Perico C, De Pierri C, Neto G, Fernandes D, Pedrosa F, de Souza E . Genomic landscape of the SARS-CoV-2 pandemic in Brazil suggests an external P.1 variant origin. Front Microbiol. 2023; 13:1037455. PMC: 9814972. DOI: 10.3389/fmicb.2022.1037455. View

16.

Bailey T, Boden M, Whitington T, Machanick P . The value of position-specific priors in motif discovery using MEME. BMC Bioinformatics. 2010; 11:179. PMC: 2868008. DOI: 10.1186/1471-2105-11-179. View

17.

Bailey T, Johnson J, Grant C, Noble W . The MEME Suite. Nucleic Acids Res. 2015; 43(W1):W39-49. PMC: 4489269. DOI: 10.1093/nar/gkv416. View

18.

Bonetti Franceschi V, Ferrareze P, Zimerman R, Cybis G, Thompson C . Mutation hotspots and spatiotemporal distribution of SARS-CoV-2 lineages in Brazil, February 2020-2021. Virus Res. 2021; 304:198532. PMC: 8654641. DOI: 10.1016/j.virusres.2021.198532. View