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

A polynomial time solvable formulation of multiple sequence alignment.

Sing-Hoi Sze1, Yue Lu, Qingwu Yang

  • 1Department of Computer Science, Texas A&M University, College Station, 77843, USA. shsze@cs.tamu.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|April 7, 2006
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

5-methoxytryptamine improves hepatic inflammation and insulin resistance in a macrophage C-X-C motif chemokine ligand 14 dependent manner.

Molecular biomedicine·2026
Same author

Efficacy and safety of early tirofiban administration after intravenous thrombolysis in patients with acute ischaemic stroke: the multicentre, randomised, double-blind, placebo-controlled RESCUE BT3 trial protocol.

European stroke journal·2026
Same author

Development and Optimisation of an HPLC-MS/MS Workflow for Profiling Selenium and Sulphur Amino Acids in Soybean Leaves and Investigation of Se-S Metabolic Interactions.

Molecules (Basel, Switzerland)·2026
Same author

Intravenous Tirofiban After Tenecteplase in Acute Ischemic Stroke: The INSTANT Randomized Clinical Trial.

JAMA·2026
Same author

Stroke Etiologies With Intravenous Thrombolysis before Thrombectomy and Functional Outcomes in Anterior Circulation Large Vessel Occlusion.

Annals of neurology·2026
Same author

Multiple Intracranial <i>Nocardia brevicatena</i> Abscesses in a Patient with a Previous History of Tuberculosis: A Case Report.

Infection and drug resistance·2026
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

This study introduces a new method for multiple sequence alignment, offering guaranteed accuracy by preserving pairwise alignments within a tree structure. This approach solves a previously NP-hard problem in polynomial time, improving alignment quality.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Traditional multiple sequence alignment methods are NP-hard, relying on heuristics with no performance guarantees.
  • This lack of guarantees complicates understanding and assessing the quality of resulting alignments.

Purpose of the Study:

  • To propose an alternative multiple alignment formulation based on preserving a specified set of pairwise alignments within a tree structure.
  • To demonstrate that this formulation, when using consistency-based pairwise alignments, achieves high accuracy and can be solved in polynomial time.

Main Methods:

  • Formulating multiple alignment as finding the shortest preserving alignment based on a given tree structure.
  • Reducing the problem to a graph-theoretic problem solvable in polynomial time.

Related Experiment Videos

  • Integrating consistency-based pairwise alignments from TCoffee and ProbCons into the preserving alignment framework.

    • Main Results:

    • The proposed preserving alignment method, when replacing heuristic steps in TCoffee and ProbCons, achieved competitive or superior accuracy on benchmark datasets.
    • Outperformed TCoffee on two out of three test sets.
    • Achieved similar or better accuracy compared to ProbCons, even without iterative refinements.

    Conclusions:

    • The preserving alignment formulation provides a polynomial-time solvable alternative to heuristic-based multiple sequence alignment.
    • This method offers guaranteed solutions and improved accuracy, particularly when incorporating consistency information.
    • The PSAlign software implements this approach, offering a reliable tool for multiple sequence alignment.