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

Indel-tolerant read mapping with trinucleotide frequencies using cache-oblivious kd-trees.

Md Pavel Mahmud1, John Wiedenhoeft, Alexander Schliep

  • 1Department of Computer Science, Rutgers University, New Jersey, USA. pavelm@cs.rutgers.edu

Bioinformatics (Oxford, England)
|September 11, 2012
PubMed
Summary

This study introduces TreQ, a novel read mapping approach using geometric embedding for faster and more accurate next-generation sequencing analysis. TreQ improves the detection of genetic variations, including structural variants, by efficiently handling large edit distances.

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

GAA-FGF14 Ataxia Is a Frequently Overlooked Cause of Sporadic Adult-Onset Ataxia.

Clinical genetics·2026
Same author

Evolution shapes and conserves genomic signatures in viruses.

Communications biology·2024
Same author

Compressed computations using wavelets for hidden Markov models with continuous observations.

PloS one·2023
Same author

Using Active Learning to Develop Machine Learning Models for Reaction Yield Prediction.

Molecular informatics·2022
Same author

Blood Glucose Prediction with Variance Estimation Using Recurrent Neural Networks.

Journal of healthcare informatics research·2022
Same author

Fast parallel construction of variable-length Markov chains.

BMC bioinformatics·2021

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Next-generation sequencing (NGS) read mapping is computationally intensive, often requiring hundreds of CPU hours.
  • Existing methods struggle with large edit distances, especially insertions and deletions (indels), hindering genetic variation analysis.

Purpose of the Study:

  • To develop a novel, efficient, and accurate read mapping algorithm for next-generation sequencing data.
  • To address the limitations of current methods in handling large edit distances and indels.

Main Methods:

  • Adoption of the approximate string matching paradigm using geometric embedding.
  • Rephrasing read mapping as nearest neighbor queries in a q-gram frequency vector space.
  • Utilizing L(1) distance for edit distance lower bounds and a cache-oblivious kd-tree for efficient querying.

Related Experiment Videos

Main Results:

  • Achieved running times comparable to state-of-the-art methods.
  • Demonstrated constant time and memory requirements for read lengths between 100 and 1000 bp.
  • TreQ showed improved accuracy over popular read mappers, particularly for detecting structural variants.

Conclusions:

  • Geometric embedding is a promising paradigm for read mapping.
  • L(1) distance can be effective for detecting structural variations.
  • TreQ offers a more accurate and efficient solution for NGS read mapping and genetic variation analysis.