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

Compressed pattern matching in DNA sequences.

Lei Chen1, Shiyong Lu, Jeffrey Ram

  • 1Wayne State University, USA. ak3230@wayne.edu

Proceedings. IEEE Computational Systems Bioinformatics Conference
|February 2, 2006
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

Metabolic rearrangement enables adaptation of microbial growth rate to temperature shifts.

Nature microbiology·2024
Same author

Metabolomic rearrangement controls the intrinsic microbial response to temperature changes.

bioRxiv : the preprint server for biology·2023
Same author

[Effect of fluoride ion on corrosion of two dental titanium alloys].

Hua xi kou qiang yi xue za zhi = Huaxi kouqiang yixue zazhi = West China journal of stomatology·2010
Same author

[Treatment of early avascular necrosis of femoral head by core decompression combined with autologous bone marrow mesenchymal stem cells transplantation].

Zhongguo xiu fu chong jian wai ke za zhi = Zhongguo xiufu chongjian waike zazhi = Chinese journal of reparative and reconstructive surgery·2010
Same author

MicroRNAome of porcine pre- and postnatal development.

PloS one·2010
Same author

Hyperactive putamen in patients with paroxysmal kinesigenic choreoathetosis: a resting-state functional magnetic resonance imaging study.

Movement disorders : official journal of the Movement Disorder Society·2010
Same journal

A Two-Step Approach for Clustering Proteins based on Protein Interaction Profile.

Proceedings. IEEE Computational Systems Bioinformatics Conference·2008
Same journal

Proceedings of 2005 IEEE Computational Systems Bioinformatics Conference. August 8-11, 2005. Stanford, California, USA.

Proceedings. IEEE Computational Systems Bioinformatics Conference·2007
Same journal

Fractal genomics modeling: a new approach to genomic analysis and biomarker discovery.

Proceedings. IEEE Computational Systems Bioinformatics Conference·2006
Same journal

Gene Ontology friendly biclustering of expression profiles.

Proceedings. IEEE Computational Systems Bioinformatics Conference·2006
Same journal

Comparative analysis of gene sets in the Gene Ontology space under the multiple hypothesis testing framework.

Proceedings. IEEE Computational Systems Bioinformatics Conference·2006
Same journal

AZuRE, a scalable system for automated term disambiguation of gene and protein names.

Proceedings. IEEE Computational Systems Bioinformatics Conference·2006
See all related articles

We developed a new compressed DNA sequence matching algorithm, derivative Boyer-Moore (d-BM), achieving over 10x speedup for long patterns and 75% space savings. This DNA pattern matching method enhances efficiency through increased alphabet size.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomic Data Analysis

Background:

  • String matching algorithms are crucial for DNA sequence analysis.
  • Existing methods face challenges with large genomic datasets and long pattern searches.
  • The Boyer-Moore algorithm is a widely used string matching technique.

Purpose of the Study:

  • To introduce a novel compressed pattern matching algorithm for DNA sequences.
  • To improve the speed and space efficiency of DNA sequence analysis.
  • To leverage the Boyer-Moore algorithm for enhanced performance in genomics.

Main Methods:

  • Developed the derivative Boyer-Moore (d-BM) algorithm.
  • Implemented a compression strategy using two bits per DNA base (A, T, C, G).

Related Experiment Videos

  • Compared d-BM performance against the Agrep exact match routine for long DNA patterns.

    • Main Results:

    • The d-BM algorithm demonstrated over 10 times faster searching for DNA patterns longer than 50 characters compared to Agrep.
    • Achieved a guaranteed 75% space saving through DNA sequence compression.
    • Enhanced algorithm speed attributed to increased alphabet size (4 to 256) improving Boyer-Moore efficiency.

    Conclusions:

    • The derivative Boyer-Moore algorithm offers significant speed and space improvements for DNA sequence pattern matching.
    • This compressed approach is highly effective for analyzing large-scale genomic data.
    • The method presents a promising advancement in bioinformatics tools for sequence analysis.