Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Evolutionary Relationships through Genome Comparisons02:54

Evolutionary 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
Genome Annotation and Assembly03:36

Genome 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

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

RAmpSim: a thermodynamic simulator for hybridization capture in metagenomic sequencing.

Bioinformatics (Oxford, England)·2026
Same author

Primer Design through Submodular Function Estimation.

Bioinformatics (Oxford, England)·2026
Same author

Accelerating String Comparison in RLZ Compressed Sequences via LCE Jumps.

bioRxiv : the preprint server for biology·2026
Same author

Socioeconomic and Clinical Determinants Driving Access to BRCA Genetic Testing in Cancer : A Case-Control Study Using Observational Electronic Health Records Across Multiple Sites.

medRxiv : the preprint server for health sciences·2026
Same author

Consistency in causal reasoning for large language models in scenarios of HIV antiretroviral treatment, drug interactions, and side effects.

NPJ digital medicine·2026
Same author

Integrating Causal Inference and Agent-Based Modelling to Assess the Impact of Clinicians' Guideline Adherence in Older Adults Hospitalized with Pneumonia.

Studies in health technology and informatics·2026

Related Experiment Video

Updated: Jun 12, 2025

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
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
PubMed
Summary
This summary is machine-generated.

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.

Keywords:
AlgorithmsBioinformaticsBiological SequencesComputational Biology

More Related Videos

G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome
06:40

G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome

Published on: March 22, 2018

5.8K
Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER
14:06

Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER

Published on: June 23, 2012

15.2K

Related Experiment Videos

Last Updated: Jun 12, 2025

Rare Event Detection Using Error-corrected DNA and RNA Sequencing
10:36

Rare Event Detection Using Error-corrected DNA and RNA Sequencing

Published on: August 3, 2018

12.0K
G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome
06:40

G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome

Published on: March 22, 2018

5.8K
Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER
14:06

Detection of Rare Genomic Variants from Pooled Sequencing Using SPLINTER

Published on: June 23, 2012

15.2K

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.