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

An exact solution for the segment-to-segment multiple sequence alignment problem.

H P Lenhof1, B Morgenstern, K Reinert

  • 1MPI für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany.

Bioinformatics (Oxford, England)
|May 1, 1999
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

In vitro perfusion of whole bovine ovaries by freezing medium: effect of perfusion rate and elapsed time after extraction.

Clinical laboratory·2013
Same author

Improved phylogenomic taxon sampling noticeably affects nonbilaterian relationships.

Molecular biology and evolution·2010
Same author

Contrast agents and applications to assess tumor angiogenesis in vivo by magnetic resonance imaging.

Current medicinal chemistry·2007
Same author

TICO: a tool for postprocessing the predictions of prokaryotic translation initiation sites.

Nucleic acids research·2006
Same author

[Analysis of Foetal Heart Rate Data using Complex Software: Comparison of Recurrence Plot of Foetal Heart Rate with the Course of Pregnancy -].

Zeitschrift fur Geburtshilfe und Neonatologie·2004
Same author

[Primary diagnosis of hormone-secreting pituitary adenoma during pregnancy and after birth -- a rare occurrence].

Zeitschrift fur Geburtshilfe und Neonatologie·2004
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

This study introduces a new method for segment-to-segment multiple sequence alignment by reformulating it as the Generalized Maximum Trace problem. The approach uses integer linear programming and polyhedral combinatorics to find optimal solutions for molecular sequence alignment.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Molecular Evolution

Background:

  • Sequence alignment is fundamental in molecular biology for understanding molecular structure, function, and species evolution.
  • The segment-to-segment variation of multiple alignment involves selecting a maximum weight set of consistent diagonals (non-gapped segment pairs).

Purpose of the Study:

  • To introduce a novel formulation of the segment-to-segment multiple sequence alignment problem as the Generalized Maximum Trace (GMT) problem.
  • To develop an optimal algorithm for segment-to-segment multiple sequence alignment, potentially improving upon existing greedy strategies.

Main Methods:

  • The segment-to-segment multiple alignment problem is shown to be equivalent to the Generalized Maximum Trace (GMT) problem.
  • The GMT problem is formulated as an integer linear program.

Related Experiment Videos

  • Methods from polyhedral combinatorics are employed to solve the integer linear program, leading to a branch-and-cut algorithm.

    • Main Results:

    • The study presents the first computational results of the novel branch-and-cut algorithm.
    • The algorithm successfully finds optimal solutions for real-world test cases in segment-to-segment multiple sequence alignment.

    Conclusions:

    • The developed branch-and-cut algorithm provides an optimal method for solving the segment-to-segment multiple sequence alignment problem.
    • This approach offers a significant advancement over previous greedy strategies for this type of molecular sequence analysis.