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

Computational complexity of multiple sequence alignment with SP-score.

W Just1

  • 1Department of Mathematics, College of Arts & Sciences, Morton Hall 321, Ohio University, Athens, OH 45701, USA. just@math.ohiou.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|December 19, 2001
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

Synchronization of non-identical systems by non-invasive mutual time-delayed feedback.

Chaos (Woodbury, N.Y.)·2023
Same author

Nonlinear dynamics of delay systems: an overview.

Philosophical transactions. Series A, Mathematical, physical, and engineering sciences·2019
Same author

[Branchio-oculo-facial syndrome].

Annales de dermatologie et de venereologie·2012
Same author

Ellobius lutescens: sex determination and sex chromosome.

Sexual development : genetics, molecular biology, evolution, endocrinology, embryology, and pathology of sex determination and differentiation·2008
Same author

Beyond the odd number limitation: a bifurcation analysis of time-delayed feedback control.

Physical review. E, Statistical, nonlinear, and soft matter physics·2007
Same author

Self-stabilization of high-frequency oscillations in semiconductor superlattices by time-delay autosynchronization.

Physical review. E, Statistical, nonlinear, and soft matter physics·2004
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

The multiple sequence alignment problem using the SP-score is NP-hard for most common scoring matrices. This computational complexity holds even with restricted sequence shifts and no internal gaps.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Analysis

Background:

  • Multiple sequence alignment is fundamental in bioinformatics for understanding protein and nucleic acid evolution.
  • The computational complexity of alignment algorithms impacts their scalability for large biological datasets.
  • Scoring matrices guide sequence alignment by quantifying residue similarities.

Purpose of the Study:

  • To determine the computational complexity of the multiple sequence alignment problem with the SP-score.
  • To investigate the impact of scoring matrices on alignment problem hardness.
  • To assess the problem's complexity under constrained alignment conditions.

Main Methods:

  • Complexity theory analysis
  • NP-hardness and MAX-SNP-hardness proofs

Related Experiment Videos

  • Examination of scoring matrix properties

    • Main Results:

    • The multiple alignment problem with SP-score is NP-hard for a broad class of scoring matrices.
    • The problem remains NP-hard even when only sequence shifts are permitted and internal gaps are disallowed.
    • A specific scoring matrix M(0) renders the multiple alignment problem MAX-SNP-hard, irrespective of internal gap allowance.

    Conclusions:

    • The SP-score based multiple sequence alignment is computationally intractable for most practical scoring matrices.
    • Algorithmic approaches for this problem face fundamental limitations, even with simplified alignment models.
    • The identified MAX-SNP-hardness suggests significant challenges in finding exact or approximate solutions.