Alignment-Free Sequence Analysis and Applications.

Genome and metagenome comparisons based on large amounts of next generation sequencing (NGS) data pose significant challenges for alignment-based approaches due to the huge data size and the relatively short length of the reads. Alignment-free approaches based on the counts of word patterns in NGS data do not depend on the complete genome and are generally computationally efficient. Thus, they contribute significantly to genome and metagenome comparison. Recently, novel statistical approaches have been developed for the comparison of both long and shotgun sequences. These approaches have been applied to many problems including the comparison of gene regulatory regions, genome sequences, metagenomes, binning contigs in metagenomic data, identification of virus-host interactions, and detection of horizontal gene transfers. We provide an updated review of these applications and other related developments of word-count based approaches for alignment-free sequence analysis.

• Publication year

  2018

• Venue

  Annual Review of Biomedical Data Science

• Publication date

  2018-03-26

• Fields of study

  Biology, Computer Science, Mathematics, Environmental Science, Medicine

• Identifiers
  DOI 10.1146/ANNUREV-BIODATASCI-080917-013431arXiv 1803.09727PMID 31828235PMCID PMC6905628
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Computation of d 2: A Measure of Sequence Dissimilarity

  2018cited by this paper
• Gene Co-occurrence Networks Reflect Bacteriophage Ecology and Evolution

  2018cited by this paper
• Alignment-free sequence comparison: benefits, applications, and tools

  2017influential reference
• Optimal choice of word length when comparing two Markov sequences using a χ2-statistic

  2017cited by this paper
• Viral Phylogenomics Using an Alignment-Free Method: A Three-Step Approach to Determine Optimal Length of k-mer

  2017cited by this paper
• Alignment-free inference of hierarchical and reticulate phylogenomic relationships

  2017cited by this paper
• An effective extension of the applicability of alignment-free biological sequence comparison algorithms with Hadoop

  2017cited by this paper
• CAFE: aCcelerated Alignment-FrEe sequence analysis

  2017influential reference
• WIsH: who is the host? Predicting prokaryotic hosts from metagenomic phage contigs

  2017cited by this paper
• Robust Inference of Genetic Exchange Communities from Microbial Genomes Using TF-IDF

  2017cited by this paper
• Improving contig binning of metagenomic data using \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {d}_2^S $$\end{doc

  2017influential reference
• Weighted measures based on maximizing deviation for alignment-free sequence comparison

  2017influential reference
• Prediction of virus-host infectious association by supervised learning methods

  2017cited by this paper
• Gene networks provide a high-resolution view of bacteriophage ecology

  2017cited by this paper
• Uncovering Earth’s virome

  2016cited by this paper
• A novel alignment-free method for detection of lateral genetic transfer based on TF-IDF

  2016cited by this paper
• Alignment-free microbial phylogenomics under scenarios of sequence divergence, genome rearrangement and lateral genetic transfer

  2016cited by this paper
• kWIP: The k-mer weighted inner product, a de novo estimator of genetic similarity

  2016influential reference
• Multiple comparative metagenomics using multiset k-mer counting

  2016cited by this paper
• Alignment-free Transcriptomic and Metatranscriptomic Comparison Using Sequencing Signatures with Variable Length Markov Chains

  2016influential reference
• Recapitulating phylogenies using k-mers: from trees to networks.

  2016cited by this paper
• An estimator for local analysis of genome based on the minimal absent word.

  2016cited by this paper
• Exploring lateral genetic transfer among microbial genomes using TF-IDF

  2016cited by this paper
• HostPhinder: A Phage Host Prediction Tool

  2016cited by this paper
• Accurate binning of metagenomic contigs via automated clustering sequences using information of genomic signatures and marker genes

  2016cited by this paper
• Computational methods for predicting genomic islands in microbial genomes

  2016cited by this paper
• Alignment-free \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{upgreek} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} }{}$d_2^*$\end{document} oligonucleotide frequency dissi

  2016cited by this paper
• Recapitulating phylogenies using k-mers: from trees to networks

  2016cited by this paper
• Metagenomic analysis of the viral community in Namib Desert hypoliths.

  2015cited by this paper
• Patterns and ecological drivers of ocean viral communities

  2015cited by this paper
• MBBC: an efficient approach for metagenomic binning based on clustering

  2015cited by this paper
• Inference of Markovian properties of molecular sequences from NGS data and applications to comparative genomics

  2015influential reference
• Computational approaches to predict bacteriophage–host relationships

  2015cited by this paper
• Inferring Horizontal Gene Transfer

  2015cited by this paper
• An assembly and alignment-free method of phylogeny reconstruction from next-generation sequencing data

  2015cited by this paper
• Mash: fast genome and metagenome distance estimation using MinHash

  2015influential reference
• Gut DNA viromes of Malawian twins discordant for severe acute malnutrition

  2015cited by this paper
• Viral dark matter and virus–host interactions resolved from publicly available microbial genomes

  2015cited by this paper
• An improved model for whole genome phylogenetic analysis by Fourier transform.

  2015cited by this paper
• Disease-specific alterations in the enteric virome in inflammatory bowel disease.

  2015cited by this paper
• Molecular phylogenetics before sequences

  2014cited by this paper
• Inferring phylogenies of evolving sequences without multiple sequence alignment

  2014influential reference
• Alignment-free genetic sequence comparisons: a review of recent approaches by word analysis

  2014cited by this paper
• Horizontally Transferred Genetic Elements and Their Role in Pathogenesis of Bacterial Disease

  2014cited by this paper
• Sequence analysis by iterated maps, a review

  2014cited by this paper
• New developments of alignment-free sequence comparison: measures, statistics and next-generation sequencing

  2014cited by this paper
• Spaced words and kmacs: fast alignment-free sequence comparison based on inexact word matches

  2014cited by this paper
• KMC 2: Fast and resource-frugal k-mer counting

  2014cited by this paper
• Fast alignment-free sequence comparison using spaced-word frequencies

  2014cited by this paper
• A highly abundant bacteriophage discovered in the unknown sequences of human faecal metagenomes

  2014cited by this paper
• High-Level Diversity of Tailed Phages, Eukaryote-Associated Viruses, and Virophage-Like Elements in the Metaviromes of Antarctic Soils

  2014cited by this paper
• The Amordad database engine for metagenomics

  2014influential reference
• MaxBin: an automated binning method to recover individual genomes from metagenomes using an expectation-maximization algorithm

  2014cited by this paper
• Large Local Analysis of the Unaligned Genome and Its Application

  2013cited by this paper
• Exact Goodness‐of‐Fit Tests for Markov Chains

  2013cited by this paper
• Information theory applications for biological sequence analysis

  2013cited by this paper
• Multiple alignment-free sequence comparison

  2013cited by this paper
• Markov Chain Order estimation with Conditional Mutual Information

  2013cited by this paper
• DSK: k-mer counting with very low memory usage

  2013cited by this paper
• Alignment-Free Genome Tree Inference by Learning Group-Specific Distance Metrics

  2013cited by this paper
• The Binning of Metagenomic Contigs for Microbial Physiology of Mixed Cultures

  2012cited by this paper
• Statistical Applications in Genetics and Molecular Biology Alignment-free Sequence Comparison for Biologically Realistic Sequences of Moderate Length

  2012cited by this paper
• One size does not fit all: On how Markov model order dictates performance of genomic sequence analyses

  2012cited by this paper
• Classification of metagenomic sequences: methods and challenges

  2012cited by this paper
• Alignment free comparison: similarity distribution between the DNA primary sequences based on the shortest absent word.

  2012cited by this paper
• Estimation of pairwise sequence similarity of mammalian enhancers with word neighbourhood counts

  2012cited by this paper
• Comparison of metagenomic samples using sequence signatures

  2012cited by this paper
• Metagenomic Analysis of a Southern Maritime Antarctic Soil

  2012cited by this paper
• Alignment-Free Sequence Comparison Based on Next-Generation Sequencing Reads

  2012cited by this paper
• A fast, lock-free approach for efficient parallel counting of occurrences of k-mers

  2011cited by this paper
• A robust and accurate binning algorithm for metagenomic sequences with arbitrary species abundance ratio

  2011cited by this paper
• Whole-genome phylogeny of Escherichia coli/Shigella group by feature frequency profiles (FFPs)

  2011influential reference
• Testing the Order of Markov Dependence in DNA Sequences

  2011cited by this paper
• The human gut virome: inter-individual variation and dynamic response to diet.

  2011cited by this paper
• New powerful statistics for alignment-free sequence comparison under a pattern transfer model.

  2011cited by this paper
• Composition vector approach to whole-genome-based prokaryotic phylogeny: success and foundations.

  2010cited by this paper
• A Benchmark of Parametric Methods for Horizontal Transfers Detection

  2010cited by this paper
• Assembly free comparative genomics of short‐read sequence data discovers the needles in the haystack

  2010cited by this paper
• Clustering metagenomic sequences with interpolated Markov models

  2010cited by this paper
• Co-phylog: an assembly-free phylogenomic approach for closely related organisms

  2010influential reference
• A Novel Construction of Genome Space with Biological Geometry

  2010cited by this paper
• Viruses in the fecal microbiota of monozygotic twins and their mothers

  2010cited by this paper
• Alignment-Free Sequence Comparison (II): Theoretical Power of Comparison Statistics

  2010influential reference
• A Novel Abundance-Based Algorithm for Binning Metagenomic Sequences Using l-tuples

  2010cited by this paper
• A fungal phylogeny based on 82 complete genomes using the composition vector method

  2009cited by this paper
• Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions

  2009influential reference
• Metagenomic signatures of 86 microbial and viral metagenomes.

  2009cited by this paper
• Unsupervised statistical clustering of environmental shotgun sequences

  2009cited by this paper
• Whole-proteome phylogeny of prokaryotes by feature frequency profiles: An alignment-free method with optimal feature resolution

  2009influential reference
• Alignment-Free Sequence Comparison (I): Statistics and Power

  2009influential reference
• Markov Chain Order Estimation and Relative Entropy

  2009cited by this paper
• Scientific Computation: Phylogenetic tree construction

  2009cited by this paper
• Whole-proteome phylogeny of large dsDNA virus families by an alignment-free method

  2009cited by this paper
• Community-wide analysis of microbial genome sequence signatures

  2009cited by this paper
• Horizontal gene transfer in eukaryotic evolution

  2008cited by this paper
• A Protein Map and Its Application

  2008cited by this paper
• Reticulate representation of evolutionary and functional relationships between phage genomes.

  2008cited by this paper
• Estimating the extent of horizontal gene transfer in metagenomic sequences

  2008cited by this paper
• 28-way vertebrate alignment and conservation track in the UCSC Genome Browser.

  2007cited by this paper
• Identification of compositionally distinct regions in genomes using the centroid method

  2007cited by this paper

• Nuclear DNA of plastid origin (NUPTs), neglected driver of genome variation and evolutionary innovation

  2026cites this paper
• Machine Learning Enables Alignment‐Free Distance Calculation and Phylogenetic Placement Using k‐Mer Frequencies

  2025cites this paper
• Uncovering position-specific patterns in codon and codon-pair usage in candidate genes associated with blood coagulation diseases.

  2025cites this paper
• Phylogeny Reconstruction Using Multi-Agent Surface Area Pressure Features

  2025cites this paper
• Estimating Genome-Wide Phylogenies Using Probabilistic Topic Modeling

  2025cites this paper
• Frequency Chaos Game Representation - Singular Value Decomposition for Alignment-Free Phylogenetic Analysis

  2025cites this paper
• Using transfer learning models for DNA sequence similarity via fCGR method

  2025cites this paper
• The Neglected Role of Heterotrophic Protists in Engineered Water Systems.

  2025cites this paper
• Applied DNA visibility graphs: Understanding DNA structure-function relationship in genomics

  2025cites this paper
• k-mer approaches for biodiversity genomics

  2025cites this paper
• Evaluation of antioxidant activity of brown macroalgae found in Lampung Bay, Indonesia and molecular identification using DNA barcode cox1 BLAST

  2025cites this paper
• A Systematic Bioinformatics Approach for Mapping the Minimal Set of a Viral Peptidome

  2024cites this paper
• DNA Sequence Similarity Using Discrete Wavelet Transform

  2024cites this paper
• TreeWave: command line tool for alignment-free phylogeny reconstruction based on graphical representation of DNA sequences and genomic signal processing

  2024cites this paper
• An alignment- and reference-free strategy using k-mer present pattern for population genomic analyses

  2024cites this paper
• Detecting genetic gain and loss events in terms of protein domain: Method and implementation

  2024cites this paper
• Utilizing genomic signatures to gain insights into the dynamics of SARS-CoV-2 through Machine and Deep Learning techniques

  2024cites this paper
• Hyperdimensional computing: A fast, robust, and interpretable paradigm for biological data

  2024cites this paper
• New groups of highly divergent proteins in families as old as cellular life with important biological functions in the ocean

  2024influential citation
• New proposal of viral genome representation applied in the classification of SARS-CoV-2 with deep learning

  2023cites this paper
• UNIQmin, an alignment-free tool to study viral sequence diversity across taxonomic lineages: a case study of monkeypox virus

  2023cites this paper
• Sequence Alignment/Map format: a comprehensive review of approaches and applications

  2023cites this paper
• DNA Matching Using k - mer Derived Spatial Features

  2023cites this paper
• DNA visibility graphs

  2023cites this paper
• (m, n)-mer—a simple statistical feature for sequence classification

  2023cites this paper
• Using alignment-free and pattern mining methods for SARS-CoV-2 genome analysis

  2023cites this paper
• Dataset Similarity to Assess Semisupervised Learning Under Distribution Mismatch Between the Labeled and Unlabeled Datasets

  2023cites this paper
• MLR-OOD: a Markov chain based Likelihood Ratio method for Out-Of-Distribution detection of genomic sequences.

  2022cites this paper
• Dataset Similarity to assess Semi-supervised Learning under Distribution Mismatch between the Labelled and Unlabelled Datasets

  2022cites this paper
• A novel part-wise template matching technique for DNA sequence similarity identification

  2022cites this paper
• Molecular Identification of the Brown Algae Sargassum sp. from the Lombok Coastal Waters

  2022cites this paper
• BioKlustering: a web app for semi-supervised learning of maximally imbalanced genomic data

  2022cites this paper
• A fast and efficient algorithm for DNA sequence similarity identification

  2022influential citation
• Michael Waterman's Contributions to Computational Biology and Bioinformatics

  2022cites this paper
• MGTdb: a web service and database for studying the global and local genomic epidemiology of bacterial pathogens

  2022cites this paper
• Alignment-Free Analysis of Whole-Genome Sequences From Symbiodiniaceae Reveals Different Phylogenetic Signals in Distinct Regions

  2022cites this paper
• Alignment-Free Sequence Comparison: A Systematic Survey From a Machine Learning Perspective

  2022cites this paper
• A generative nonparametric Bayesian model for whole genomes

  2021cites this paper
• Forest and Trees: Exploring Bacterial Virulence with Genome-wide Association Studies and Machine Learning.

  2021cites this paper
• CVTree: A Parallel Alignment-free Phylogeny and Taxonomy Tool Based on Composition Vectors of Genomes

  2021cites this paper
• Tiara: deep learning-based classification system for eukaryotic sequences

  2021cites this paper
• COVID-19 Genome Analysis Using Alignment-Free Methods

  2021cites this paper
• DNA Sequences Classification with Deep Learning: A Survey

  2021cites this paper
• Inferring Phylogenomic Relationship of Microbes Using Scalable Alignment-Free Methods.

  2021cites this paper
• On universal algorithms for classifying and predicting stationary processes

  2021cites this paper
• A Computational Framework for Pattern Detection on Unaligned Sequences: An Application on SARS-CoV-2 Data

  2021cites this paper
• Exploring the Limits of Out-of-Distribution Detection

  2021cites this paper
• Metagenomics: a path to understanding the gut microbiome

  2021cites this paper
• Taxonomy classification using genomic footprint of mitochondrial sequences.

  2021cites this paper
• Genome-wide alignment-free phylogenetic distance estimation under a no strand-bias model

  2021cites this paper
• Lessons Learnt From Using the Machine Learning Random Forest Algorithm to Predict Virulence in Streptococcus pyogenes

  2021cites this paper
• Sensitivity of A Frequency-Based Alignment-Free Approach For Phylogeny Rreconstruction.

  2021cites this paper
• Alignment-free Phylogeny Reconstruction Based On Quartet Trees

  2020cites this paper
• Automatic Identification of SARS Coronavirus using Compression-Complexity Measures

  2020cites this paper
• Classifying the Lifestyle of Metagenomically-Derived Phages Sequences Using Alignment-Free Methods

  2020cites this paper
• A Generalized Iterative Map for Analysis of Protein Sequences.

  2020cites this paper
• KITSUNE: A Tool for Identifying Empirically Optimal K-mer Length for Alignment-Free Phylogenomic Analysis

  2020cites this paper
• CRAFT: Compact genome Representation towards large-scale Alignment-Free daTabase

  2020cites this paper
• Specificity Analysis of Genome Based on Statistically Identical K-Words With Same Base Combination

  2020cites this paper
• A Graphical Representation of Protein Sequences and Its Applications

  2020cites this paper
• MixMOOD: A systematic approach to class distribution mismatch in semi-supervised learning using deep dataset dissimilarity measures

  2020cites this paper
• Positional Correlation Natural Vector: A Novel Method for Genome Comparison

  2020cites this paper
• A2G2: A Python wrapper to perform very large alignments in semi-conserved regions

  2020cites this paper
• GenFooT: Genomic Footprint of mitochondrial sequence for Taxonomy classification

  2020cites this paper
• A New Numerical Method for DNA Sequence Analysis Based on 8-Dimensional Vector Representation

  2019cites this paper
• S-conLSH: alignment-free gapped mapping of noisy long reads

  2019cites this paper
• Sequence Comparison without Alignment: The SpaM approaches

  2019cites this paper
• GRaphical Footprint Based Alignment-Free Method (GRAFree) for Classifying the Species in Large-Scale Genomics

  2019cites this paper
• Reads Binning Improves Alignment-Free Metagenome Comparison

  2019cites this paper
• Computer-Assisted and Data Driven Approaches for Surveillance, Drug Discovery, and Vaccine Design for the Zika Virus

  2019cites this paper
• Large-scale network analysis captures biological features of bacterial plasmids

  2019cites this paper
• Likelihood Ratios for Out-of-Distribution Detection

  2019cites this paper
• A geometric characterization of DNA sequence

  2019cites this paper
• Benchmarking of alignment-free sequence comparison methods

  2019cites this paper
• RAFTS3G: an efficient and versatile clustering software to analyses in large protein datasets

  2019cites this paper
• Read-SpaM: assembly-free and alignment-free comparison of bacterial genomes with low sequencing coverage

  2019cites this paper
• Alignment-free approaches for predicting novel Nuclear Mitochondrial Segments (NUMTs) in the human genome.

  2019cites this paper
• ‘Multi-SpaM’: a maximum-likelihood approach to phylogeny reconstruction using multiple spaced-word matches and quartet trees

  2019cites this paper
• The number of k-mer matches between two DNA sequences as a function of k and applications to estimate phylogenetic distances

  2019cites this paper
• Afann: bias adjustment for alignment-free sequence comparison based on sequencing data using neural network regression

  2019cites this paper
• The number of k -mer matches between two DNA sequences as a function of k

  2019cites this paper
• A new method for rapid genome classification, clustering, visualization, and novel taxa discovery from metagenome

  2019cites this paper
• Hierarchical Clustering of DNA k-mer Counts in RNAseq Fastq Files Identifies Sample Heterogeneities

  2018cites this paper
• What is Biomedical Data Science and Do We Need an Annual Review of It?

  2018cites this paper
• Science as a Culinary Art: How Data Science and Informatics Will Change Knowledge Discovery for Everyone

  2018cites this paper
• Comparison of Compression-Based Measures with Application to the Evolution of Primate Genomes

  2018cites this paper
• Metagenomic Composition Analysis of an Ancient Sequenced Polar Bear Jawbone from Svalbard

  2018cites this paper
• Multi-SpaM: a Maximum-Likelihood approach to Phylogeny reconstruction based on Multiple Spaced-Word Matches

  2018cites this paper
• Prot-SpaM: fast alignment-free phylogeny reconstruction based on whole-proteome sequences

  2018cites this paper
• Multi-SpaM: A Maximum-Likelihood Approach to Phylogeny Reconstruction Using Multiple Spaced-Word Matches and Quartet Trees

  2018cites this paper
• Alignment-Free Approaches for Predicting Novel Nuclear Mitochondrial Segments (NUMTs) in the Human Genome

  2017cites this paper
• CAFE: aCcelerated Alignment-FrEe sequence analysis

  2017cites this paper
• k-mer Similarity, Networks of Microbial Genomes, and Taxonomic Rank

  2017cites this paper