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

Settling the intractability of multiple alignment.

Isaac Elias1

  • 1Department of Numerical Analysis and Computer Science, KTH, Stockholm, Sweden. isaac@nada.kth.se

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

Improved electronic uniformity and nanoscale homogeneity in template-grown CsPbBr<sub>3</sub> nanorods.

Nanoscale·2024
Same author

Yield of diagnostic testing in evaluating etiology and end organ effects of pediatric hypertension.

Pediatric nephrology (Berlin, Germany)·2023
Same author

Multiple sclerosis risk perception and acceptance for Brazilian patients.

Arquivos de neuro-psiquiatria·2018
Same author

Fastphylo: fast tools for phylogenetics.

BMC bioinformatics·2013
Same author

Inferring horizontal transfers in the presence of rearrangements by the minimum evolution criterion.

Bioinformatics (Oxford, England)·2008
Same author

Reconstruction of ancestral genomic sequences using likelihood.

Journal of computational biology : a journal of computational molecular cell biology·2007
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 proves the NP-hardness for key multiple sequence alignment variations, including SP-score, star, and tree alignment. These findings are crucial for understanding the computational complexity of biological sequence analysis.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Analysis

Background:

  • Multiple sequence alignment is fundamental in computational biology.
  • Existing research often cites NP-hardness but lacks proofs for basic variations.
  • The computational complexity of common alignment problems remains incompletely understood.

Purpose of the Study:

  • To establish the NP-hardness for prevalent multiple sequence alignment variations.
  • To address the lack of hardness proofs for elementary alignment problems.
  • To provide a comprehensive understanding of the computational limits in sequence alignment.

Main Methods:

  • Demonstrating NP-hardness for specific alignment problems.
  • Utilizing reductions from known NP-hard problems.

Related Experiment Videos

  • Analyzing variations including SP-score, star, and tree alignment.

    • Main Results:

    • NP-hardness is proven for MULTIPLE ALIGNMENT WITH SP-SCORE, STAR ALIGNMENT, and TREE ALIGNMENT across various metrics and alphabets.
    • NP-hardness is also established for CONSENSUS PATTERNS and SUBSTRING PARSIMONY.
    • The study settles the NP-hardness for previously unproven elementary variations.

    Conclusions:

    • The most common variations of multiple sequence alignment are computationally intractable (NP-hard).
    • These results have significant implications for the development of efficient algorithms and heuristics in bioinformatics.
    • Further research may focus on approximation algorithms or specialized cases where alignment is tractable.