Related Experiment Video
Updated: Jun 12, 2025
10:36
Rare Event Detection Using Error-corrected DNA and RNA Sequencing
Published on: August 3, 2018
12.0K
An average-case efficient two-stage algorithm for enumerating all longest common substrings of minimum length k
Mattia Prosperi1, Simone Marini1, Christina Boucher2
1dept. of Epidemiology, University of Florida, Gainesville, FL (USA).
Proceedings. IEEE International Conference on Healthcare Informatics
|September 23, 2024
Summary
This study introduces an efficient algorithm for finding all longest common substrings (ALCS) of a minimum length in large biological texts. The new method offers significant speed advantages for genomic analysis, especially with divergent genomes.
Area of Science:
- Bioinformatics
- Computational Biology
- Genomics
Background:
- The longest common substring (LCS) problem is fundamental in bioinformatics.
- Enumerating all longest common substrings (ALCS) of a minimum length is crucial for discovering genetic signatures in large biological texts like genomes and metagenomes.
- Existing methods may not be efficient for very long sequences.
Purpose of the Study:
- To develop an efficient two-stage algorithm for the ALCS-k problem, which enumerates all common substrings of at least length k.
- To provide a scalable solution for analyzing large genomic and metagenomic datasets.
- To offer insights into biological mechanisms through the discovery of genetic signatures.
Main Methods:
- A novel two-stage algorithm is presented, leveraging the spectrum of k-mers (substrings of length k).
- The first stage involves efficient k-mer spectrum analysis with log-linear time complexity.
- The second stage focuses on identifying common k-mers with average-case log-linear time complexity, significantly reducing the search space.
Main Results:
- The algorithm achieves log-linear time complexity in the number of k-mers for the first stage and average-case log-linear time complexity in the number of common k-mers for the second stage.
- Space complexity is linear in the first phase (disk-based) and on average linear in the second phase (disk- and memory-based).
- Empirical tests on various genomes demonstrate run times consistent with theoretical estimates and show an asymptotic advantage over MUMmer4 for divergent genomes.
Conclusions:
- The proposed ALCS-k algorithm is efficient and scalable for analyzing large biological sequences.
- It provides a valuable tool for identifying genetic signatures and understanding biological mechanisms.
- The method demonstrates superior performance compared to existing tools like MUMmer4, particularly for divergent genomes.
Related Concept Videos
02:54Evolutionary Relationships through Genome Comparisons
5.7K
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...
5.7K
03:36Genome Annotation and Assembly
18.8K
The genome refers to all of the genetic material in an organism. It can range from a few million base pairs in microbial cells to several billion base pairs in many eukaryotic organisms. Genome assembly refers to the process of taking the DNA sequencing data and putting it all back together in a correct order to create a close representation of the original genome. This is followed by the identification of functional elements on the newly assembled genome, a process called genome annotation.
18.8K