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

Optimizing multiple spaced seeds for homology search.

Jinbo Xu1, Daniel Brown, Ming Li

  • 1School of Computer Science, University of Waterloo, Waterloo, ON, Canada. j3xu@tti-c.org

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|October 14, 2006
PubMed
Summary

Optimized spaced seeds enhance local homology search sensitivity and specificity. A linear programming algorithm provides a mathematical foundation for seed selection, improving performance over greedy methods.

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

The Local Anesthetic Bupivacaine Inhibits the Progression of Non-Small Cell Lung Cancer by Inducing Autophagy Through Akt/mTOR Signaling.

Frontiers in oncology·2021
Same author

Light exposure mediates circadian rhythms of rhizosphere microbial communities.

The ISME journal·2021
Same author

Novel Potent Selective Orally Active S1P5 Receptor Antagonists.

ACS medicinal chemistry letters·2021
Same author

Biodegradable metals for bone fracture repair in animal models: a systematic review.

Regenerative biomaterials·2021
Same author

Rectangular multilayer dielectric gratings with broadband high diffraction efficiency and enhanced laser damage resistance.

Optics express·2021
Same author

Invariant Image Representation Using Novel Fractional-Order Polar Harmonic Fourier Moments.

Sensors (Basel, Switzerland)·2021

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Sequence Analysis

Background:

  • Multiple seeds generally offer improved sensitivity and specificity over single seeds in local homology searches.
  • Existing methods for optimizing seed selection lack theoretical guarantees and mathematical foundations.

Purpose of the Study:

  • To develop and evaluate a linear programming (LP)-based algorithm for optimizing sets of spaced seeds.
  • To provide a theoretical performance guarantee for the proposed seed optimization method.

Main Methods:

  • Formulation of an optimization problem for selecting spaced seeds.
  • Application of linear programming to find an optimal or near-optimal set of seeds.
  • Theoretical analysis of the algorithm's performance guarantee.

Related Experiment Videos

Main Results:

  • The LP-based algorithm theoretically guarantees at least 70% of optimal sensitivity in most models.
  • In practice, the algorithm achieves solutions within 90% of the optimal.
  • The proposed method outperforms or matches greedy algorithms in performance.

Conclusions:

  • The developed LP-based algorithm provides a mathematically grounded approach for optimizing spaced seeds.
  • This method significantly improves sensitivity and specificity in local homology searches.
  • The algorithm offers a robust and efficient solution for seed selection in bioinformatics.