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 methods for multiple sequence alignment with guaranteed error bounds

D Gusfield1

  • 1Computer Science Division, University of California, Davis 95616-8755.

Bulletin of Mathematical Biology
|January 1, 1993
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

Inference of haplotypes from samples of diploid populations: complexity and algorithms.

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

A practical algorithm for optimal inference of haplotypes from diploid populations.

Proceedings. International Conference on Intelligent Systems for Molecular Biology·2000
Same author

Constructing additive trees when the error is small.

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

Parametric and inverse-parametric sequence alignment with XPARAL.

Methods in enzymology·1996

This study presents efficient computational methods for multiple sequence alignment, guaranteeing results within a factor of two of the optimal alignment. These algorithms aid in identifying conserved biological patterns and inferring evolutionary histories.

Area of Science:

  • Computational biology
  • Bioinformatics
  • Genomics

Background:

  • Multiple sequence alignment is crucial for identifying conserved patterns and evolutionary relationships in biological sequences.
  • Existing methods for optimal multiple sequence alignment are computationally inefficient for large datasets.
  • Several measures exist to evaluate alignment quality, but efficient optimal computation remains a challenge.

Purpose of the Study:

  • To develop computationally efficient methods for multiple sequence alignment.
  • To provide guaranteed bounds on the deviation from optimal alignment.
  • To address challenges in pattern discovery and evolutionary inference from biological sequences.

Main Methods:

  • Developed two novel, computationally efficient algorithms for multiple sequence alignment.

Related Experiment Videos

  • Algorithms guarantee alignment quality within a factor of two from the optimal value.
  • Introduced a related randomized method for faster computation with high-probability error bounds.

    • Main Results:

    • Achieved guaranteed error bounds significantly less than two, especially for a small number of sequences (e.g., 1.33 for three sequences).
    • The randomized method offers substantial speed improvements with reliable error bounds.
    • One method provides a non-obvious lower bound for the optimal alignment score.

    Conclusions:

    • The developed methods offer efficient and reliable solutions for multiple sequence alignment.
    • These algorithms advance the capabilities for pattern discovery and evolutionary analysis in computational biology.
    • The guaranteed performance bounds provide a novel and valuable feature for practical applications.