pith. sign in

arxiv: 2606.02408 · v1 · pith:KAAZPWIKnew · submitted 2026-06-01 · 💻 cs.CC · q-bio.QM

Structure-Informed Multiple Sequence Alignment: A Formal Model and Hardness Results

Yoshiki Kanazawa , Naphan Benchasattabuse , Michal Hajdu\v{s}ek , Rodney Van Meter This is my paper

Pith reviewed 2026-06-28 11:38 UTC · model grok-4.3

classification 💻 cs.CC q-bio.QM
keywords multiple sequence alignmentNP-completenessstructure-informedcontact map overlapapproximation hardnesscomputational complexitybioinformatics algorithms
0
0 comments X

The pith

The structure-informed multiple sequence alignment decision problem is NP-complete for fixed scoring schemes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a structure-informed multiple sequence alignment problem that adds a binary overlap score for designated position pairs to standard fixed string scoring with affine gaps. It establishes that the decision version is NP-complete for a wide range of fixed scoring rules, even when all position-pair sets are nonempty. The optimization version has no polynomial-time approximation scheme for two input strings under the unit scoring scheme, unless P equals NP. These results set a formal complexity baseline for incorporating structural information into alignment tasks.

Core claim

MSA-S-DEC is NP-complete for a broad class of fixed pairwise string scoring schemes, and MSA-S-OPT(lambda) admits no PTAS even for k=2 under the canonical unit scheme unless P=NP.

What carries the argument

The MSA-S model that combines a fixed pairwise string score with a binary overlap score on designated position-pairs.

If this is right

  • Structure-informed alignment cannot be solved exactly in polynomial time for general instances.
  • Even for two sequences, no efficient approximation is possible under standard assumptions.
  • Hardness holds when requiring positive overlap thresholds and nonempty pair sets.
  • The model provides a baseline showing that structural contact information increases computational difficulty.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practical implementations must rely on heuristics or restrictions to special cases.
  • Similar NP-hardness may extend to other problems that integrate sequence and structure data.
  • Parameterized algorithms or fixed-parameter tractability could be explored for small numbers of sequences or specific scoring rules.

Load-bearing premise

The pairwise string scoring rule and affine gap penalties are fixed constants independent of the input instances, and the overlap score is a simple binary function on designated position-pairs.

What would settle it

A polynomial-time algorithm that solves MSA-S-DEC for any of the fixed scoring schemes covered by the proof would show the claim is false.

read the original abstract

We formulate a structure-informed multiple sequence alignment problem, denoted MSA-S. The model abstracts biological sequences as strings and structural information as designated position-pairs. It augments a fixed pairwise string score, defined by a fixed non-gap symbol-pair scoring rule and fixed affine gap penalties, with a binary overlap score on designated position-pairs, which can be interpreted as a contact-map overlap score in structural applications. This yields a fixed-score, integer-valued optimization model suitable for complexity-theoretic analysis. Under this formulation, we show that the decision problem MSA-S-DEC is NP-complete for a broad class of fixed pairwise string scoring schemes. We also show that NP-hardness persists even under the restriction that every designated position-pair set is nonempty and the pair-overlap threshold is strictly positive. For the associated scalarized optimization problem MSA-S-OPT(lambda) with any fixed rational constant lambda >= 1, we further show that, under the canonical unit scheme for the non-gap symbol-pair scoring rule, MSA-S-OPT(lambda) admits no polynomial-time approximation scheme (PTAS) even for two input strings (k = 2), unless P = NP. These results establish a formal complexity-theoretic baseline for structure-informed multiple sequence alignment.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper formulates the structure-informed multiple sequence alignment problem MSA-S. It augments a fixed pairwise string score (non-gap symbol-pair rule plus fixed affine gap penalties) with a binary overlap score on designated position-pairs. The authors prove that the decision problem MSA-S-DEC is NP-complete for a broad class of fixed pairwise scoring schemes, with the hardness persisting even when every designated position-pair set is nonempty and the overlap threshold is strictly positive. They further show that the scalarized optimization problem MSA-S-OPT(lambda) admits no PTAS for any fixed rational lambda >= 1, even when restricted to k=2 input strings, under the canonical unit scheme, unless P=NP. These results are positioned as a formal complexity-theoretic baseline for structure-informed MSA.

Significance. If the proofs hold, the work supplies a clean, parameter-free complexity baseline for an important variant of multiple sequence alignment that incorporates structural contact information. The fixed-score model and explicit separation between the pairwise string component and the binary overlap term allow the hardness statements to apply broadly without hidden instance dependence. Such results are useful for guiding algorithm design and for clarifying the limits of approximation in structural bioinformatics applications.

minor comments (1)
  1. [Abstract] The abstract states the main theorems clearly but does not indicate the high-level proof strategy (e.g., which classic NP-complete problem is reduced from). Adding one sentence on the reduction source would improve readability without lengthening the abstract appreciably.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive recommendation to accept and for the accurate summary of the paper's contributions. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines a formal optimization model MSA-S with fixed scoring components (non-gap symbol-pair rules and affine gap penalties as constants, plus a binary overlap term) and proves NP-completeness of MSA-S-DEC plus inapproximability of MSA-S-OPT(lambda) via standard polynomial-time reductions from known NP-hard problems. These are external to the paper's own inputs; no parameter fitting, no self-definitional equations, no load-bearing self-citations, and no renaming of empirical patterns. The derivation chain consists of explicit reductions that remain independent of the target result, making the complexity claims self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are described.

pith-pipeline@v0.9.1-grok · 5767 in / 974 out tokens · 14483 ms · 2026-06-28T11:38:37.111704+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references

  1. [1]

    Multiple sequence alignment modeling: methods and applications.Briefings in Bioinformatics, 17(6):1009–1023, 2016

    Maria Chatzou, Cedrik Magis, Jia-Ming Chang, Carsten Kemena, Giovanni Bussotti, Ionas Erb, and Cedric Notredame. Multiple sequence alignment modeling: methods and applications.Briefings in Bioinformatics, 17(6):1009–1023, 2016

    2016

  2. [2]

    Developments in algorithms for sequence alignment: A review.Biomolecules, 12(4):546, 2022

    Jiannan Chao, Furong Tang, and Lei Xu. Developments in algorithms for sequence alignment: A review.Biomolecules, 12(4):546, 2022

    2022

  3. [3]

    Revisiting evaluation of multiple sequence alignment methods

    Tandy Warnow. Revisiting evaluation of multiple sequence alignment methods. In Kazutaka Katoh, editor,Multiple Sequence Alignment, volume 2231 ofMethods in Molecular Biology. Humana, 2021

    2021

  4. [4]

    Cambridge University Press, 1998

    Richard Durbin, Sean Eddy, Anders Stærmose Krogh, and Graeme Mitchison.Biologi- cal Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998

    1998

  5. [5]

    An improved algorithm for matching biological sequences.Journal of Molecular Biology, 162(3):705–708, 1982

    Osamu Gotoh. An improved algorithm for matching biological sequences.Journal of Molecular Biology, 162(3):705–708, 1982

    1982

  6. [6]

    Needleman and Christian D

    Saul B. Needleman and Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins.Journal of Molecular Biology, 48(3):443–453, 1970

    1970

  7. [7]

    T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195–197, 1981

    1981

  8. [8]

    On the complexity of multiple sequence alignment

    Lusheng Wang and Tao Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1(4):337–348, 1994

    1994

  9. [9]

    Computational complexity of multiple sequence alignment with sp-score.Journal of Computational Biology, 8(6):615–623, 2001

    Winfried Just. Computational complexity of multiple sequence alignment with sp-score.Journal of Computational Biology, 8(6):615–623, 2001. 20

    2001

  10. [10]

    Settling the intractability of multiple alignment.Journal of Computational Biology, 13(7):1323–1339, 2006

    Isaac Elias. Settling the intractability of multiple alignment.Journal of Computational Biology, 13(7):1323–1339, 2006

    2006

  11. [11]

    Edgar and Serafim Batzoglou

    Robert C. Edgar and Serafim Batzoglou. Multiple sequence alignment.Current Opinion in Structural Biology, 16(3):368–373, 2006

    2006

  12. [12]

    A survey on sequence alignment algorithms and state-of-the- art aligners.ACM Computing Surveys, 58(3), 2025

    Konstantinos Prousalis, Konstantinos Georgiou, Andreas Kalogeropoulos, Dimitrios Ntalaperas, Nikos Konofaos, Lefteris Angelis, Christos Papalitsas, Thanos Stavropou- los, and Nico Gariboldi. A survey on sequence alignment algorithms and state-of-the- art aligners.ACM Computing Surveys, 58(3), 2025

    2025

  13. [13]

    Higgins, and Cédric Notredame

    Orla O’Sullivan, Karsten Suhre, Chantal Abergel, Desmond G. Higgins, and Cédric Notredame. 3dcoffee: Combining protein sequences and structures within multiple sequence alignments.Journal of Molecular Biology, 340(2):385–395, 2004

    2004

  14. [14]

    Jimin Pei, Bong-Hyun Kim, and Nick V. Grishin. Promals3d: a tool for multiple protein sequence and structure alignments.Nucleic Acids Research, 36(7):2295–2300, 2008

    2008

  15. [15]

    Standley, and Kazutaka Katoh

    John Rozewicki, Songling Li, Karlou Mar Amada, Daron M. Standley, and Kazutaka Katoh. Mafft-dash: integrated protein sequence and structural alignment.Nucleic Acids Research, 47(W1):W5–W10, 2019

    2019

  16. [16]

    Protein multiple alignments: sequence- based versus structure-based programs.Bioinformatics, 35(20):3970–3980, 2019

    Mathilde Carpentier and Jacques Chomilier. Protein multiple alignments: sequence- based versus structure-based programs.Bioinformatics, 35(20):3970–3980, 2019

    2019

  17. [17]

    Papadimitriou

    Deborah Goldman, Sorin Istrail, and Christos H. Papadimitriou. Algorithmic aspects of protein structure similarity. InProceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 512–521, 1999

    1999

  18. [18]

    Proof verification and the hardness of approximation problems.Journal of the ACM, 45(3):501–555, 1998

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems.Journal of the ACM, 45(3):501–555, 1998. 21

    1998