Yang Young Lu, Kujin Tang, Jie Ren et al. · Nucleic Acids Research · 2017
Alignment-free genome and metagenome comparisons are increasingly important with the development of next generation sequencing (NGS) technologies. Recently developed state-of-the-art k-mer based alignment-free dissimilarity measures including CVTree, $d_2^*$ and $d_2^S$ are more computationally expensive than measures based solely on the k-mer frequencies. Here, we report a standalone software, aCcelerated Alignment-FrEe sequence analysis (CAFE), for efficient calculation of 28 alignment-free dissimilarity measures. CAFE allows for both assembled genome sequences and unassembled NGS shotgun reads as input, and wraps the output in a standard PHYLIP format. In downstream analyses, CAFE can also be used to visualize the pairwise dissimilarity measures, including dendrograms, heatmap, principal coordinate analysis and network display. CAFE serves as a general k-mer based alignment-free analysis platform for studying the relationships among genomes and metagenomes, and is freely available at https://github.com/younglululu/CAFE.
Cited by 76Open access
Jie Ren, Xin Bai, Yang Young Lu et al. · arXiv (Cornell University) · 2018
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.
Cited by 3Open access
Isabel Schwende, Tuan D. Pham · Briefings in Bioinformatics · 2013
With the massive production of genomic and proteomic data, the number of available biological sequences in databases has reached a level that is not feasible anymore for exact alignments even when just a fraction of all sequences is used. To overcome this inevitable time complexity, ultrafast alignment-free methods are studied. Within the past two decades, a broad variety of nonalignment methods have been proposed including dissimilarity measures on classical representations of sequences like k-words or Markov models. Furthermore, articles were published that describe distance measures on alternative representations such as compression complexity, spectral time series or chaos game representation. However, alignments are still the standard method for real world applications in biological sequence analysis, and the time efficient alignment-free approaches are usually applied in cases when the accustomed algorithms turn out to fail or be too inconvenient.
Cited by 32Open access
Emre Delibaş · Journal of Molecular Graphics and Modelling · 2025
Cited by 4
Emre DELIBAŞ · Sigma Journal of Engineering and Natural Sciences – Sigma Mühendislik ve Fen Bilimleri Dergisi · 2022
Improvements in technology have triggered the production of big data. Within this scope, enormous amounts of biological data have been generated. A number of analysis methods have been developed to access the information contained in biological data. DNA sequence analysis has drawn particular attention in recent years. As an alternative to alignment-based sequence comparison methods that have high computational costs, alignment-free comparison methods have emerged. These m ethods c an c alculate sequence s imilarity by applying different dimensions of numerical characterizations. In this paper, we propose a novel alignment-free DNA sequence analysis method based on a feature extraction strategy. The method utilizes numerical characterization and is implemented by calculating mean distance of the transitions, mean distance of the nucleotide duplications, and the base frequencies. The method then measures the similarity between 7-dimensional vectors that are obtained through feature extraction. Using this approach, we conducted a sequence similarity analysis of two different DNA sequence datasets of different lengths to demonstrate the effectiveness of the method. The proposed method shows that a simple and successful feature vector can be obtained when DNA sequences having many properties are used in combination with appropriate and effective descriptors. With this strategy, reasonable results were obtained with a low computational cost.
Cited by 5Open access
Kahkashan Kouser, Lalitha Rangarajan · 2016
Advancement in the DNA sequencing machinery has led to tremendous accumulation of sequence data. This has encouraged researchers to develop more robust analysis methods. Promoter sequences are an important part of these DNA sequences which take part in gene expression and regulation. Here, we attempt to perform alignment free variance based feature selection on Position Specific Motif Matrices of promoter sequences. Then, we analyze similarity/differences existing in these sequences using the cumulative distribution of the selected features/motifs. To demonstrate the efficacy of the proposed technique we use promoter data from NCBI database. The similarity/dissimilarity values get enhanced when we use only the selected features/motifs instead of all the features. Hence, the combination of feature selection and analysis using cumulative distribution of motifs proposed for promoter sequence analysis has the potential to enhance the similarity/differences that exist between promoter sequences.
Cited by 0
Kshatrapal Singh, Ashish Kumar, Manoj Gupta et al. · Journal of Pharmaceutical Negative Results · 2022
Phylogenetic analysis explains how species evolved throughout time. Multiple sequence alignments of proteins or genomes can be used to infer a phylogenetic tree. Understanding evolution requires phylogenetics, or reconstructing organisms' evolutionary relationships. The alignment of complete gene sequences of higher eukaryotes, as well as the construction of phylogenetic trees on the basis of these alignments, is a computationally costly and ambitious undertaking. To get around these restrictions, we compared the genomes of the Brassicales clade using alignment-free technique. A Chaos Representation (CR) can be evaluated for each nucleotide sequence, which depicts each nucleotide as a point in a square specified by the four nucleotides as nodes. As a result, every CR is a distinct fingerprint of the basic sequence. Each grid square in the CRs represents the presence of oligonucleotides of a given size in the sequence if the CRs are categorized by grid lines (Frequency Chaos Representation, FCR). To build phylogenetic trees of Brassicales species, we used distance metrics between FCRs.
Cited by 0Open access
Wu Wen · 2010
Based on the distribution of K-tuple in complete genome, a method without doing sequence alignment to infer difference of biological sequence is proposed in this paper. The method can be used to measure the difference of distribution on K-tuple between the native DNA sequences and the corresponding randomized ones. Applied to construct phylogenetic trees of the complete mitochondrial genomes of 26 species of placental mammals, with K increasing, it yields phylogenetic trees of which the classification effect increasingly matches the result widely recognised by the biological field. The final results show that the phylogenetic trees built by this method is more reasonable than by other alignment-free sequence methods.
Cited by 1
Oliver Bonham-Carter, J. L. Steele, Dhundy Bastola · Briefings in Bioinformatics · 2013
Modern sequencing and genome assembly technologies have provided a wealth of data, which will soon require an analysis by comparison for discovery. Sequence alignment, a fundamental task in bioinformatics research, may be used but with some caveats. Seminal techniques and methods from dynamic programming are proving ineffective for this work owing to their inherent computational expense when processing large amounts of sequence data. These methods are prone to giving misleading information because of genetic recombination, genetic shuffling and other inherent biological events. New approaches from information theory, frequency analysis and data compression are available and provide powerful alternatives to dynamic programming. These new methods are often preferred, as their algorithms are simpler and are not affected by synteny-related problems. In this review, we provide a detailed discussion of computational tools, which stem from alignment-free methods based on statistical analysis from word frequencies. We provide several clear examples to demonstrate applications and the interpretations over several different areas of alignment-free analysis such as base-base correlations, feature frequency profiles, compositional vectors, an improved string composition and the D2 statistic metric. Additionally, we provide detailed discussion and an example of analysis by Lempel-Ziv techniques from data compression.
Cited by 134Open access
Jayanta Kumar Das, Antara Sengupta, Pabitra Pal Choudhury et al. · Gene · 2020
Cited by 18
Klas Hatje, Martin Kollmar · Frontiers in Plant Science · 2012
Phylogenetic analyses reveal the evolutionary derivation of species. A phylogenetic tree can be inferred from multiple sequence alignments of proteins or genes. The alignment of whole genome sequences of higher eukaryotes is a computational intensive and ambitious task as is the computation of phylogenetic trees based on these alignments. To overcome these limitations, we here used an alignment-free method to compare genomes of the Brassicales clade. For each nucleotide sequence a Chaos Game Representation (CGR) can be computed, which represents each nucleotide of the sequence as a point in a square defined by the four nucleotides as vertices. Each CGR is therefore a unique fingerprint of the underlying sequence. If the CGRs are divided by grid lines each grid square denotes the occurrence of oligonucleotides of a specific length in the sequence (Frequency Chaos Game Representation, FCGR). Here, we used distance measures between FCGRs to infer phylogenetic trees of Brassicales species. Three types of data were analyzed because of their different characteristics: (A) Whole genome assemblies as far as available for species belonging to the Malvidae taxon. (B) EST data of species of the Brassicales clade. (C) Mitochondrial genomes of the Rosids branch, a supergroup of the Malvidae. The trees reconstructed based on the Euclidean distance method are in general agreement with single gene trees. The Fitch-Margoliash and Neighbor joining algorithms resulted in similar to identical trees. Here, for the first time we have applied the bootstrap re-sampling concept to trees based on FCGRs to determine the support of the branchings. FCGRs have the advantage that they are fast to calculate, and can be used as additional information to alignment based data and morphological characteristics to improve the phylogenetic classification of species in ambiguous cases.
Cited by 65Open access
Emre Delibaş, Ahmet Arslan, Abdulkadir Şeker et al. · Journal of Molecular Graphics and Modelling · 2020
Cited by 23
Jan P. Radomski, Piotr P. Słonimski · Comptes Rendus Biologies · 2009
Synonymous codons do not occur at equal frequencies. Codon usage and codon bias have been extensively studied. However, the sequential order in which synonymous codons appear within a gene has not been studied until now. Here we describe an in silico method, which is the first attempt to tackle this problem: to what extent this sequential order is unique, and to what extent the succession of synonymous codons is important. This method, which we called Intragenic, Stochastic Synonymous Codon Occurrence Replacement (ISSCOR), generates, by a Monte Carlo approach, a set of genes which code for the same amino acid sequence, and display the same codon usage, but have random permutations of the synonymous codons, and therefore different sequential codon orders from the original gene. We analyze the complete genome of the bacterium Helicobacter pylori (containing 1574 protein coding genes), and show by various, alignment-free computational methods (e.g., frequency distribution of codon-pairs, as well as that of nucleotide bigrams in codon-pairs), that: (i) not only the succession of adjacent synonymous codons is far from random, but also, which is totally unexpected, the occurrences of non-adjacent synonymous codon-pairs are highly constrained, at strikingly long distances of dozens of nucleotides; (ii) the statistical deviations from the random synonymous codon order are overwhelming; and (iii) the pattern of nucleotide bigrams in codon-pairs can be used in a novel way for characterizing and comparing genes and genomes. Our results demonstrate that the sequential order of synonymous codons within a gene must be under a strong selective pressure, which is superimposed on the classical codon usage. This new dimension can be measured by the ISSCOR method, which is simple, robust, and should be useful for comparative and functional genomics.
Cited by 3
Jie Zhou, Pianyu Zhong, Tinghui Zhang · Evolutionary Bioinformatics · 2016
Determination of sequence similarity is one of the major steps in computational phylogenetic studies. One of the major tasks of computational biologists is to develop novel mathematical descriptors for similarity analysis. DNA clustering is an important technology that automatically identifies inherent relationships among large-scale DNA sequences. The comparison between the DNA sequences of different species helps determine phylogenetic relationships among species. Alignment-free approaches have continuously gained interest in various sequence analysis applications such as phylogenetic inference and metagenomic classification/clustering, particularly for large-scale sequence datasets. Here, we construct a novel and simple mathematical descriptor based on the characterization of cis sequence complex DNA networks. This new approach is based on a code of three cis nucleotides in a gene that could code for an amino acid. In particular, for each DNA sequence, we will set up a cis sequence complex network that will be used to develop a characterization vector for the analysis of mitochondrial DNA sequence phylogenetic relationships among nine species. The resulting phylogenetic relationships among the nine species were determined to be in agreement with the actual situation.
Cited by 16Open access
Susana Vinga · 2016
Biological sequence analysis is at the core of bioinformatics, bringing together several fields, from computer science to probability and statistics. Its purpose is to computationally process and decode the information stored in biological macromolecules involved in all cell mechanisms of living organisms – such as DNA, RNA and proteins – and provide prediction tools to reveal their structure, function and complex relationship networks. Within this context several methods have arisen that analyze sequences based on alignment algorithms, ubiquitously used in most bioinformatics applications. Alternatively, although less explored in the literature, the use of vector maps for the analysis of biological sequences, both DNA and proteins, represents a very elegant proposal to extract information from those types of sequences using an alignment-free approach. This work presents an overview of alignment-free methods used for sequence analysis and comparison and the new trends of these techniques, applied to DNA and proteins. The recent endeavors found in the literature along with new proposals and widening of applications fully justifies a revisit to these methodologies, partially reviewed before
Cited by 0
M. Brittnacher, Sonya L. Heltshe, Hillary S. Hayden et al. · PLoS ONE · 2016
Because clinical efficacy of the transplant procedure cannot be fully evaluated without analysis methods to quantify actual FMT engraftment, we developed a method for detecting change in the gut microbiome that is independent of species identification and database bias, sensitive to changes in relative abundance of the microbial constituents, and can be formulated as an index for correlating engraftment success with clinical measures of disease. More generally, this method may be applied to clinical evaluation of human microbiomes and provide potential diagnostic determination of individuals who may be candidates for specific therapies directed at alteration of the microbiome.
Cited by 9Open access
Gurjit S. Randhawa, Kathleen A. Hill, Lila Kari · Bioinformatics · 2019
Supplementary data are available at Bioinformatics online.
Cited by 30Open access
Juan Shen, Wenwu Wu, Xiaoli Xie et al. · Hereditas (Beijing) · 2010
Based on the distribution of K-tuple in complete genome, a method without doing sequence alignment to infer difference of biological sequence is proposed in this paper. The method can be used to measure the difference of distribution on K-tuple between the native DNA sequences and the corresponding randomized ones. Applied to construct phylogenetic trees of the complete mitochondrial genomes of 26 species of placental mammals, with K increasing, it yields phylogenetic trees of which the classification effect increasingly matches the result widely recognised by the biological field. The final results show that the phylogenetic trees built by this method is more reasonable than by other alignment-free sequence methods.
Cited by 1
Gurjit S. Randhawa, Kathleen A. Hill, Lila Kari · bioRxiv (Cold Spring Harbor Laboratory) · 2019
Abstract Summary MLDSP-GUI (Machine Learning with Digital Signal Processing) is an open-source, alignment-free, ultrafast, computationally lightweight, standalone software tool with an interactive Graphical User Interface (GUI) for comparison and analysis of DNA sequences. MLDSP-GUI is a general-purpose tool that can be used for a variety of applications such as taxonomic classification, disease classification, virus subtype classification, evolutionary analyses, among others. Availability MLDSP-GUI is open-source, cross-platform compatible, and is available under the terms of the Creative Commons Attribution 4.0 International license ( http://creativecommons.org/licenses/by/4.0/ ). The executable and dataset files are available at https://sourceforge.net/projects/mldsp-gui/ . Contact grandha8@uwo.ca Supplementary information Supplementary data are available online.
Cited by 3Open access
Pandurang Kolekar, Mohan Kale, Urmila Kulkarni‐Kale · Molecular Phylogenetics and Evolution · 2012
Cited by 59