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 Experiment Videos

An Eulerian path approach to local multiple alignment for DNA sequences.

Yu Zhang1, Michael S Waterman

  • 1Department of Mathematics, University of Southern California, 1042 West 36th Place, DRB289, Los Angeles, CA 90089-1113, USA.

Proceedings of the National Academy of Sciences of the United States of America
|January 26, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

RNA Secondary Structures with Given Motif Specification: Combinatorics and Algorithms.

Bulletin of mathematical biology·2023
Same author

Levenshtein Distance, Sequence Comparison and Biological Database Search.

IEEE transactions on information theory·2021
Same author

Multiscale Feedback Loops in SARS-CoV-2 Viral Evolution.

Journal of computational biology : a journal of computational molecular cell biology·2020
Same author

Benchmarking of alignment-free sequence comparison methods.

Genome biology·2019
Same author

A new statistic for efficient detection of repetitive sequences.

Bioinformatics (Oxford, England)·2019
Same author

Generalized correlation measure using count statistics for gene expression data with ordered samples.

Bioinformatics (Oxford, England)·2017
Same journal

Tau protein as a regulator of mitochondrial function and dynamics.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

A scalable, dividing cell model for the robust propagation and quantification of human sporadic Creutzfeldt-Jakob disease prions.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Epigenetic regulation of mesenchymal BMP signaling directs postnatal organ innervation.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Single-shot wide-field biochemical imaging at 1 kHz frame rate.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Morphogenesis and topological evolution of a frustrated nematic liquid crystal under confinement.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

B cell-intrinsic CXCR3 drives efficient generation of ectopic pulmonary germinal center responses to influenza A virus infection.

Proceedings of the National Academy of Sciences of the United States of America·2026
See all related articles

This study introduces an efficient Eulerian path method for local multiple sequence alignment of DNA. It accurately detects conserved regions in large datasets, outperforming existing methods in speed and accuracy.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Local multiple sequence alignment is computationally intensive for large datasets.
  • Existing methods struggle with scalability for thousands of sequences or millions of letters.

Purpose of the Study:

  • To develop an efficient and scalable method for local multiple sequence alignment of DNA sequences.
  • To accurately detect conserved regions, including short, long, conserved, and degenerate patterns, even if not present in single sequences.

Main Methods:

  • Constructing a De Bruijn graph to represent DNA sequences.
  • Utilizing Eulerian paths to identify conserved segments within the graph.
  • Applying a Poisson heuristic to assess the statistical significance of alignments.

Related Experiment Videos

Main Results:

  • The Eulerian path approach exhibits near-linear computational time and memory usage, enabling analysis of massive datasets.
  • The method successfully identified Alu repeats in the human genome, showing good agreement with RepeatMasker.
  • Demonstrated robustness and superior efficiency and accuracy compared to other alignment methods.

Conclusions:

  • The Eulerian path approach offers a highly efficient and accurate solution for local multiple sequence alignment of large-scale DNA data.
  • This method advances the detection of conserved genomic regions and facilitates large-scale genomic analysis.