{"id":"f375d7d5-dd8b-490d-af02-cf1295b9b916","arxiv_id":"2606.02408","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"MSA-S is NP-complete under broad fixed scoring schemes and admits no PTAS for MSA-S-OPT(lambda) even with k=2 unless P=NP.","lead":"The paper defines a structure-informed multiple sequence alignment problem (MSA-S) that adds a binary overlap score on designated position-pairs to standard fixed pairwise string scoring with affine gaps. It proves NP-completeness of the decision version and inapproximability of the optimization version even for two strings.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader correctly flags absence of proofs as the reason for UNVERDICTED. Without the detailed reductions, no load-bearing technical flaw can be isolated; the abstract-level claims are consistent with the stated model.","tokens_in":1722,"tokens_out":200,"duration_ms":14271,"concrete_test":"Locate the reduction for MSA-S-DEC in the full manuscript and confirm that the chosen fixed scoring scheme (non-gap symbol pairs plus affine gaps) is identical for every constructed instance and does not encode instance-specific values.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract presents a well-scoped formal model with fixed scoring components and states NP-completeness plus inapproximability results. No internal inconsistency, hidden dependence on instance-specific parameters, or unsupported modeling assumption is visible in the given formulation. The distinction between fixed pairwise scores and the binary overlap term is maintained explicitly.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1739,"tokens_out":337,"duration_ms":19043,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Abstract"}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[],"tokens_in":1291,"tokens_out":46,"duration_ms":8898,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing here is that the authors define MSA-S by layering a binary overlap score on designated position pairs onto a fixed pairwise string score with affine gaps, then prove the decision version is NP-complete for a broad class of those fixed schemes and that the scalarized optimization has no PTAS even for two strings under the unit scheme.\n\nWhat stands out as new is the precise combination: the overlap term is a simple binary function on pre-designated pairs, kept separate from the string scoring which stays constant across instances. That setup lets them carry over standard alignment hardness while adding the structure component without introducing instance-dependent parameters. The restriction to nonempty pair sets and positive thresholds, plus the k=2 inapproximability, looks like a targeted extension of earlier MSA complexity work.\n\nThe model itself is presented clearly and the claims are scoped tightly, which helps. The fixed-score requirement avoids the usual pitfalls where scoring rules could be tuned to the input.\n\nThe obvious soft spot is that the abstract states the results without any reduction outline or proof sketch, so the actual technical steps remain unchecked from this text alone. If the reductions turn out to be loose or miss edge cases in the overlap handling, that would weaken the baseline claim, but nothing in the stated assumptions signals an internal problem.\n\nThis is for readers who care about complexity baselines for alignment variants that incorporate contact maps or similar structure data. Someone designing approximation algorithms for structural MSA would find the no-PTAS result for k=2 directly useful as a limit. It is worth sending to a serious referee because the formalization is reproducible and the hardness statements are precise enough to check.","headline":"The paper proves NP-completeness for MSA-S-DEC under fixed scores and no PTAS for the optimization version even at k=2, using a clean model that adds binary overlap to standard alignment.","tokens_in":2233,"tokens_out":418,"would_cite":false,"duration_ms":13330,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The structure-informed multiple sequence alignment decision problem is NP-complete for fixed scoring schemes.","keywords":["multiple sequence alignment","NP-completeness","structure-informed","contact map overlap","approximation hardness","computational complexity","bioinformatics algorithms"],"falsifier":"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.","tokens_in":2632,"feed_emoji":"","tokens_out":530,"duration_ms":22395,"temperature":0.7,"pith_summary":"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.","feed_headline":"Structure-informed alignment is NP-complete for fixed scores","feed_subtitle":"The problem has no PTAS even for two sequences unless P=NP, establishing a complexity baseline.","key_machinery":"The MSA-S model that combines a fixed pairwise string score with a binary overlap score on designated position-pairs.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Structure-informed MSA NP-complete for fixed scores","No PTAS for structure-informed MSA at k=2","MSA-S-DEC NP-complete across fixed scoring schemes","Structure-informed alignment lacks PTAS unless P=NP"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Structure-informed MSA NP-complete for fixed scores","No PTAS for structure-informed MSA at k=2","MSA-S-DEC NP-complete across fixed scoring schemes","Structure-informed alignment lacks PTAS unless P=NP"]},"model":"grok-4.3","cost_usd":0.008099,"raw_usage":{"total_tokens":3664,"prompt_tokens":634,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":80987000,"prompt_tokens_details":{"text_tokens":634,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2970,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":634,"tokens_out":60,"duration_ms":20974,"temperature":1.0,"reasoning_tokens":2970,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T11:38:37.111704+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}