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

Efficient large-scale sequence comparison by locality-sensitive hashing.

J Buhler1

  • 1Department of Computer Science and Engineering, University of Washington, Seattle, WA 98195-2350, USA. jbuhler@cs.washington.edu

Bioinformatics (Oxford, England)
|May 2, 2001
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

Signatures of transient Wannier-Stark localization in bulk gallium arsenide.

Nature communications·2018
Same author

[Feedback of ultrasound and RMI in the staging of endometrial carcinoma in early stage].

Gynecologie, obstetrique & fertilite·2015
Same author

[Breast cancer treated by antibiotherapy? Granulomatous mastitis with Corynebacterium].

Journal de gynecologie, obstetrique et biologie de la reproduction·2015
Same author

A systematic review on the effects of air polishing devices on oral tissues.

International journal of dental hygiene·2015
Same author

A systematic review on the patient perception of periodontal treatment using air polishing devices.

International journal of dental hygiene·2015
Same author

Determinants of haemodialysis access survival.

VASA. Zeitschrift fur Gefasskrankheiten·2010
Same journal

conMItion: an R package adjusting confounding factors for associations in multi-omics.

Bioinformatics (Oxford, England)·2026
Same journal

SpaMFG: a Spatial Multi-omics Integration Method based on Feature Grouping.

Bioinformatics (Oxford, England)·2026
Same journal

CSCN: Inference of Cell-Specific Causal Networks Using Single-Cell RNA-Seq Data.

Bioinformatics (Oxford, England)·2026
Same journal

Sparse CCA-Based Mediation Analysis with High-Dimensional Exposures and Mediators.

Bioinformatics (Oxford, England)·2026
Same journal

Enhancing Cross-Context Generalization in Drug Perturbation Prediction with a Multimodal Conditional Diffusion Framework.

Bioinformatics (Oxford, England)·2026
Same journal

Primer Design through Submodular Function Estimation.

Bioinformatics (Oxford, England)·2026
See all related articles

A new algorithm, LSH-ALL-PAIRS, efficiently finds local alignments in large genomic DNA sequences. This method improves sensitivity for detecting conserved genome features with substitutions, enhancing genome comparison and annotation.

Area of Science:

  • Genomics
  • Bioinformatics
  • Computational Biology

Background:

  • Comparing large genomic DNA sequences aids in identifying and annotating conserved genome features.
  • Existing algorithms struggle to balance efficiency and sensitivity when finding local alignments with substitutions in long sequences.
  • Current methods rely on exact matches, which are prone to random occurrences in background sequences, limiting detection of features without long exact matches.

Purpose of the Study:

  • To introduce a novel algorithm, LSH-ALL-PAIRS, for efficient and sensitive detection of ungapped local alignments in genomic sequences.
  • To enable the identification of conserved genomic features with a specified fraction of substitutions, even in large sequences.
  • To overcome the limitations of existing algorithms that trade off sensitivity for efficiency.

Related Experiment Videos

Main Methods:

  • Development of the LSH-ALL-PAIRS algorithm utilizing locality-sensitive hashing (LSH).
  • Application of a randomized search technique to efficiently find ungapped local alignments.
  • Parameter selection for alignment length and substitution rate to optimize for significant similarities while minimizing background noise.

Main Results:

  • LSH-ALL-PAIRS successfully identifies ungapped local alignments in genomic sequences up to tens of megabases.
  • The algorithm demonstrates efficiency and sensitivity, detecting similarities with as low as 63% identity in mammalian genomic sequences.
  • The chosen parameters allow alignments to be frequent in significant similarities but rare in background sequences.

Conclusions:

  • LSH-ALL-PAIRS offers an efficient and sensitive approach for comparative genomics on large DNA sequences.
  • The algorithm enhances the ability to find and annotate conserved genome features, particularly those with substitutions.
  • This method advances the field of genomic sequence comparison by improving the detection of subtle similarities.