{"id":"325a59be-c1d6-4faa-a2c0-4fc756e0dd70","arxiv_id":"cs/0603105","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Seed sensitivity can be computed by dynamic programming over a product of three automata, and the new subset seeds admit a compact automaton and outperform spaced seeds in sensitivity experiments.","lead":"Sequence search tools use short patterns, called seeds, to find similar DNA regions; this paper presents a general way to compute how often a seed finds what it should. It also defines a new kind of seed that can tell apart different DNA letter changes, and shows these seeds improve sensitivity in tests.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Subset seeds' claimed search advantage rests on an untested transfer: Section 4.2 shows only in-model sensitivity, and the 'similarity search' experiments asserted in Section 5 are not reported.","rationale":"The paper's core contribution is a uniform automaton-based reduction of seed sensitivity to a DP over a product automaton (Lemmas 1 and 2) plus a compact subset-seed automaton with O((w+1)2^r) states (Lemma 4). I checked the constructions: the transition function in Section 3.2 preserves the stated invariant, the state-count identity in Lemma 4 is arithmetically correct, and the DP complexity bound follows from the transition count of the product automaton. The HMM/transducer equivalence and the induction in Lemma 3 are only sketched, but neither is load-bearing: the algorithm works directly on transducers, and Lemma 3's claim is independently checkable. The load-bearing weak point is the application-level claim. Section 4.2 optimizes seeds against transducers trained on the same 40 bacterial genomes and then reports sensitivities under those very transducers; this is an in-sample comparison. The abstract promises better similarity search results, but no search experiment is presented, and Section 5's reference to 'different experiments' lacks specifics. Thus the practical advantage depends on an untested transfer from model sensitivity to real search. This matches the reader's weakest assumption, and a held-out end-to-end search test would settle it. If that test fails, the paper would still be a valid algorithmic contribution, but the abstract's application claim would need to be downgraded.","tokens_in":11262,"tokens_out":14608,"duration_ms":123155,"concrete_test":"Run an end-to-end homology search with a seed-based aligner (e.g., YASS or equivalent) on a held-out set of genomes not used for training the Section 4.2 transducers. For a fixed weight w (e.g., w=9), compare the best subset seed from Tables 2–5 against the best ordinary spaced seed of the same weighted selectivity, using true-positive rate at equal false-positive rate. Also report whether the sensitivity advantage (e.g., 0.5253 vs 0.5420 under NT) reproduces on the held-out data; if it does not, the 'better results in similarity search' claim is conditional on the trained models.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central mathematical framework is sound, but the abstract's claim that subset seeds can be used in similarity search producing better results than ordinary spaced seeds is not supported by the reported experiments. Section 4.2 trains four probability transducers on pairwise alignments of 40 bacterial genomes, then optimizes seeds against the same transducers and reports the resulting sensitivity in Tables 2–5. This is an in-sample evaluation on the training distribution. No end-to-end similarity search is described anywhere; Section 5 merely asserts that 'different experiments' confirm the method's use in DNA similarity search, without presenting data or methodology. If the sensitivity computed under these trained transducers does not transfer to real search (e.g., because the models overfit the 40 training genomes, or because the weighted selectivity equivalence between a subset seed with two @s and an ordinary spaced seed of the same weight is not preserved in practice), then the paper's central practical advantage is unestablished. The algorithmic contribution (Lemmas 1–4) does not depend on this, but the abstract's headline application does. This is the load-bearing gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a general automata-based framework for computing the sensitivity of a seed in homology search. The seed sensitivity problem is decomposed into three components, each represented by a finite automaton: a deterministic acyclic automaton for the target alignment language, a probability transducer for the distribution over alignments, and a deterministic automaton for the language of alignments matched by the seed. Lemma 1 and Lemma 2 show that the sensitivity can be computed as a sum over full paths in a product automaton, with time complexity O(|QG|^2 |QK| |A|). The authors then introduce subset seeds, in which seed positions can match subsets of the alignment alphabet, and define an automaton Sπ recognizing the matched alignments with at most (w+1)2^r states. Experiments compare automaton sizes and report sensitivity values for spaced seeds and subset seeds with two @ positions under four probability transducers trained on bacterial genomes. The abstract claims that sensitive subset seeds can be efficiently designed and then used in similarity search with better results than ordinary spaced seeds.","tokens_in":11391,"tokens_out":10860,"duration_ms":102502,"significance":"If the algorithmic claims hold, the framework is a genuinely useful unification: it separates the alignment language, the probability model, and the seed model, and reduces sensitivity computation to a single acyclic DP. The subset-seed automaton construction with a state bound independent of the alignment alphabet is a concrete algorithmic contribution that could simplify sensitivity computation for non-binary alphabets. The preliminary experiments give in-model evidence that subset seeds can achieve higher sensitivity than spaced seeds of the same ad-hoc weight. However, the headline practical claim that subset seeds improve real similarity search is not demonstrated by the reported experiments, which evaluate sensitivity only on the trained probability models. The paper would be strengthened by an end-to-end search benchmark or by a more cautious statement of the practical conclusions.","major_comments":[{"comment":"The abstract's claim that designed subset seeds 'can then be used in similarity search producing better results than ordinary spaced seeds' is not supported by any reported experiment. Section 4.2 trains four probability transducers on pairwise alignments of 40 bacterial genomes, optimizes seeds against the same transducers, and reports the resulting sensitivity values in Tables 2-5. These are in-sample evaluations on the training distribution. Section 5 asserts that 'different experiments we have done confirm ... using those seeds for DNA similarity search', but no end-to-end search experiment, dataset, search procedure, or results are described anywhere. The sensitivity improvements in Tables 2-5 do not by themselves establish search-level improvement, since the trained models may overfit the 40 genomes and the ad-hoc weight assignment for @ may not correspond to equal selectivity in practice. The practical conclusion should either be substantiated with a real homology-search benchmark or removed from the abstract and discussion.","section":"Section 4.2 and Section 5"},{"comment":"The proof of correctness of the subset-seed automaton Sπ is only a one-sentence assertion: 'It can be verified by induction that the invariant condition on the states <X,t> is preserved by the transition function.' This automaton is load-bearing for all subset-seed results, so the induction needs to be written out explicitly. In particular, the proof must explain why the transition for a=1 leaves X unchanged, how matches ending entirely inside a run of 1s are captured by the final-state condition max{X}+t=m, and what convention is used for max(∅) when X is empty. As written, a reader cannot verify that Sπ accepts exactly the language of alignments matched by π.","section":"Section 3.2, Lemma 3"},{"comment":"The equivalence of non-deterministic probability transducers and HMMs 'with respect to the class of generated probability distributions' is asserted without proof, and the claim that the proofs are 'straightforward and are omitted due to space limitations' is not enough for a journal version. This equivalence is part of the paper's claim that the framework subsumes earlier HMM-based sensitivity algorithms, so a precise statement of the correspondence, including initial-state probabilities and termination behavior, should be provided or accompanied by a complete reference.","section":"Section 2.2"}],"minor_comments":[{"comment":"The product automaton is defined as K × G in Definition 3, but Lemma 1 writes W = G × K; please make the notation consistent.","section":"Definition 3 and Lemma 1"},{"comment":"The statement of Lemma 2 contains typos in the automaton K: 'q0t' and 'ψQ' should presumably be 'q0K' and 'ψK'. Please correct them.","section":"Lemma 2"},{"comment":"In the definition of final states, max{X} is undefined when X=∅; the later state count implies the convention max(∅)=0, but this should be stated explicitly.","section":"Section 3.2"},{"comment":"Table 1 reports average numbers of states over seeds of span up to w+8 for spaced seeds and w+5 with two @'s for subset seeds, but does not state the number of seeds averaged or any measure of variance; adding these details would improve reproducibility.","section":"Section 4.1"},{"comment":"The comparison of subset seeds and ordinary spaced seeds uses the ad-hoc weights 1, 0.5, and 0 for #, @, and respectively. Since actual selectivity under the target probability model is not simply the numeric weight, the claim that the seeds are of 'equivalent selectivity' should be justified or rephrased.","section":"Section 4.2"},{"comment":"Section 5 states that the transition table of Sπ can be constructed in O(w2^r|A|) time, while Section 3.2 says the straightforward generation takes O(rw2^r|A|) and a more complicated algorithm reduces it; please clarify which construction is used in the experiments.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reads as an extended abstract rather than a full journal paper. The main algorithmic idea is sound and the automaton state bound is valuable, but the missing induction proof, the asserted HMM-transducer equivalence, and the unsupported end-to-end search claim all need to be addressed before the paper can be accepted. The experimental comparison would be much more convincing if it included a real similarity-search benchmark rather than only in-model sensitivity on the training transducers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper is worth knowing about. It gives a unified automata-based framework for computing seed sensitivity that cleanly subsumes the DP algorithms of Buhler et al. and Brejova et al., and it introduces subset seeds, a useful middle ground between spaced and vector seeds with a genuinely compact automaton. Lemmas 1 and 2 are straightforward and correct: once the alignment language, probability transducer, and seed language are finite automata, sensitivity reduces to a path-sum DP on a product automaton. The subset-seed automaton construction is the real new result — O((w+1)2^r) states regardless of alignment alphabet size, beating the natural Aho-Corasick construction on non-binary alphabets and doing fine even on binary. The authors' table of automaton sizes gives good evidence the construction is practical.\n\nThe soft spots are not in the theory. Lemma 3's proof is a sketch, and the claim that probability transducers and HMMs are equivalent in expressiveness is asserted without proof. Both are likely repairable in a full version. The larger concern is the experimental support for the abstract's headline claim that subset seeds \"produce better results than ordinary spaced seeds\" in similarity search. Section 4.2 trains four probability transducers on pairwise alignments of forty bacterial genomes, designs seeds against those same transducers, and reports the best in-model sensitivity in Tables 2–5. That is an in-sample evaluation. No end-to-end similarity search is reported anywhere, and Section 5 merely says \"different experiments\" confirm the method's usefulness for DNA similarity search. The sensitivity gains under the trained models may well transfer, but that transfer is asserted, not demonstrated. No code, parameters, or dataset are provided either, so the experimental claims are not independently checkable.\n\nIf I were editing, I would send this to peer review. The mathematical contribution is solid and deserves full proofs. The experimental section needs either actual search results plus data/artifacts, or the claims need to be softened to \"sensitivity improvement under the trained models.\" The paper is useful for anyone working on seed design or homology search; the framework is a nice conceptual unification, not a paradigm shift.","headline":"Useful unifying framework and a genuinely compact subset-seed automaton, but the practical claim about similarity search outruns the in-sample experiments that are actually reported.","tokens_in":12033,"tokens_out":2073,"would_cite":true,"duration_ms":18512,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Seed sensitivity reduces to one dynamic program once alignments, probabilities, and seed are encoded as three finite automata; a new subset-seed automaton makes the cost independent of the alignment alphabet.","keywords":["seed sensitivity","subset seeds","spaced seeds","finite automata","probability transducer","dynamic programming","homology search","Hidden Markov Model"],"falsifier":"Run a held-out homology search comparing the designed subset seeds with the best ordinary spaced seeds of the same weight and measure true positives at a fixed false-positive rate; if the subset seeds do not find more true homologs, the transfer of sensitivity gains to search is refuted. Independently, computing the sensitivity of one seed by exhaustive enumeration over all length-64 alignments under a held-out probability model and comparing it with the dynamic-programming value would test the automaton product itself.","tokens_in":10977,"feed_emoji":"🧬","tokens_out":15562,"duration_ms":126127,"temperature":0.7,"pith_summary":"This paper claims that seed sensitivity—the probability that a random alignment is detected by a seed—can be computed by a single general algorithm, provided three ingredients are each described by a finite automaton: the set of target alignments, the probabilistic model that generates alignments, and the class of alignments a seed matches. The argument packages the three automata into one weighted product graph; the desired probability is just the total weight of all accepting paths, computed by dynamic programming in time polynomial in the automaton sizes. The payoff is that new seed definitions and new alignment distributions can be combined without re-deriving a specialized dynamic program. Applying this to subset seeds, which match positions by symbol classes rather than binary match/mismatch, the paper constructs a seed automaton whose size is independent of the alignment alphabet and at most $(w+1)2^{r}$ states, and reports designed subset seeds with higher sensitivity than ordinary spaced seeds of the same weight on DNA models trained from bacterial genomes.","feed_headline":"Subset seeds beat spaced seeds at the same design cost","feed_subtitle":"One dynamic program over three automata computes sensitivity and designs more sensitive seeds.","key_machinery":"The load-bearing mechanism is the probability-weighted product automaton $W = K \\times G$ built from the deterministic automaton $K$ recognizing $L_T\\cap L_\\pi$ and the probability transducer $G$. Its transitions follow the letter of $K$ and carry the probabilities of $G$, and because $K$ is deterministic, full paths in $W$ from the initial state to a final state are in bijection with words of $L_T\\cap L_\\pi$, each weighted by its transducer probability. Lemma 1 restates this as equality between the target probability and the total weight of all full paths; Lemma 2 adds that the target-alignment automaton $T$ is acyclic, so this total weight can be obtained by one dynamic-programming scan. The second central object is the subset-seed automaton $S_\\pi$, whose states are pairs $(X,t)$ recording which non-# positions of the seed currently match suffixes of the alignment and the length of the trailing run of matches. This encoding keeps the state count at most $(w+1)2^{r}$ regardless of the alignment alphabet, which gives subset-seed sensitivity evaluation the same asymptotic cost as ordinary spaced seeds.","core_discovery":"The central claim is Lemma 2: if target alignments form a finite regular language $L_T$ recognized by an acyclic DFA $T$, a probability transducer $G$ assigns probabilities to alignments, and a seed automaton $S_\\pi$ recognizes the alignments matched by seed $\\pi$, then the sensitivity $PG(L_T\\cap L_\\pi)/PG(L_T)$ can be computed in time $O(|Q_G|^2 |Q_K| |A|)$ and space $O(|Q_G||Q_K|)$, where $K=T\\cap S_\\pi$. The proof is a path-counting argument: determinism of $K$ gives each accepted word exactly one accepting path, so summing the path weights in the acyclic product automaton $G\\times K$ accumulates $PG(L_T\\cap L_\\pi)$ exactly. For subset seeds over an arbitrary alignment alphabet, the paper defines a DFA $S_\\pi$ with at most $(w+1)2^{r}$ states, where $w$ counts mandatory match positions and $r$ counts the remaining positions; this bound is independent of the alphabet size and matches the worst-case state count of earlier spaced-seed automata. The authors report that, in their experimental design over four probability transducers trained on 40 bacterial genomes, the best subset seed of each weight has higher sensitivity than the best ordinary spaced seed, with gains up to 0.04.","pith_inferences":["Beyond the paper, the same product construction would let seed families, multi-seed criteria, or group-hit criteria be plugged in merely by supplying their regular language, turning seed-family design into the same path-weight computation.","Because the subset-seed automaton size does not depend on the alignment alphabet, protein alignments with many symbol classes could be handled by the same sensitivity DP; the paper lists protein search as future work rather than demonstrating it.","A natural testable extension is to hold out a probability model different from the four trained transducers and compare predicted sensitivity with brute-force enumeration over all length-$n$ alignments, separating the correctness of the automaton product from the accuracy of the biological model.","One could use the same DP to sweep the weight/selectivity trade-off of a seed automatically, producing a ROC-style curve instead of a single optimal seed; the paper does not report such a sweep."],"forward_implications":["Any combination of a regular seed language, a regular target-alignment language, and a probability transducer equivalent to a Hidden Markov Model can be evaluated by the same dynamic program, so new settings do not require a new specialized derivation.","Subset-seed sensitivity carries the same worst-case complexity as ordinary spaced seeds, so alphabet-rich alignment models such as match/transition/transversion add no asymptotic cost to seed evaluation.","The subset-seed automaton is never larger than the earlier multiple-pattern automaton construction and is, in the reported experiments, substantially smaller on average, which reduces memory during seed design.","Prior spaced-seed sensitivity algorithms, including Markov and HMM-based ones, can be viewed as instances of the same framework, giving a common basis for comparing seed models.","For each weight tested under the four trained transducers, the best subset seed with two @ positions has higher sensitivity than the best ordinary spaced seed, with gains up to 0.04."],"supporting_citations":[{"why":"defines spaced seeds and the seed sensitivity estimation problem that the whole paper addresses.","marker":"[2]"},{"why":"introduces the automaton-based dynamic programming for spaced-seed sensitivity that the framework generalizes.","marker":"[17]"},{"why":"brings up the common dynamic-programming approach to seed sensitivity that the paper subsumes.","marker":"[14]"},{"why":"supplies the classical dynamic programming over acyclic graphs used to sum full-path probabilities in Lemma 2.","marker":"[20]"},{"why":"provides the multiple-pattern automaton construction used as a seed automaton and later compared with the subset-seed automaton.","marker":"[22]"},{"why":"gives the HMM-based spaced-seed sensitivity algorithm whose state triples correspond to the product construction.","marker":"[15]"},{"why":"introduces the match/transition/transversion alignment alphabet and hit criteria that motivate subset seeds.","marker":"[12]"},{"why":"provides the probability transducers B, DT1, DT2, and NT used in the seed-design experiments.","marker":"[23]"}],"fun_headline_variants":["Subset seeds outshine spaced seeds in sensitivity","Same design cost, subset seeds give higher sensitivity","Unified automata framework yields sensitive subset seeds","Subset seeds: better sensitivity at no extra cost","Seed sensitivity unified: subset seeds outperform spaced"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the probability transducers trained on pairwise alignments of forty bacterial genomes describe the alignments a real homology search will encounter; if real alignments follow a different distribution, the designed subset seeds may not outperform ordinary spaced seeds in actual search.","fun_headline_variants_meta":{"raw":{"variants":["Subset seeds outshine spaced seeds in sensitivity","Same design cost, subset seeds give higher sensitivity","Unified automata framework yields sensitive subset seeds","Subset seeds: better sensitivity at no extra cost","Seed sensitivity unified: subset seeds outperform spaced"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000769,"raw_usage":{"total_tokens":3389,"prompt_tokens":911,"completion_tokens":2478,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":2407}},"tokens_in":527,"tokens_out":2478,"duration_ms":16963,"temperature":1.0,"reasoning_tokens":2407,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-28T18:08:03.185743+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a held-out homology search comparing the designed subset seeds with the best ordinary spaced seeds of the same weight and measure true positives at a fixed false-positive rate; if the subset seeds do not find more true homologs, the transfer of sensitivity gains to search is refuted. Independently, computing the sensitivity of one seed by exhaustive enumeration over all length-64 alignments under a held-out probability model and comparing it with the dynamic-programming value would test the automaton product itself.","supporting_citations":[{"cited_title":"Bioinformatics 18 (2002) 440–445","cited_arxiv_id":null,"evidence_quote":"defines spaced seeds and the seed sensitivity estimation problem that the whole paper addresses."},{"cited_title":"In: Proceedings of the 7th Annual International Confer ence on Computa- tional Molecular Biology, ACM Press (2003) 67–75","cited_arxiv_id":null,"evidence_quote":"introduces the automaton-based dynamic programming for spaced-seed sensitivity that the framework generalizes."},{"cited_title":"to appear in Discrete Applied Mathematics (2002)","cited_arxiv_id":null,"evidence_quote":"brings up the common dynamic-programming approach to seed sensitivity that the paper subsumes."},{"cited_title":"Addison-Wesley, Reading (1974)","cited_arxiv_id":null,"evidence_quote":"supplies the classical dynamic programming over acyclic graphs used to sum full-path probabilities in Lemma 2."},{"cited_title":"Communications of the ACM 18 (1975) 333–340","cited_arxiv_id":null,"evidence_quote":"provides the multiple-pattern automaton construction used as a seed automaton and later compared with the subset-seed automaton."},{"cited_title":"Journal of Bioinformatics and Computational Biol ogy 1 (2004) 595–610","cited_arxiv_id":null,"evidence_quote":"gives the HMM-based spaced-seed sensitivity algorithm whose state triples correspond to the product construction."},{"cited_title":"BMC Bioinformatics 5 (2004)","cited_arxiv_id":null,"evidence_quote":"introduces the match/transition/transversion alignment alphabet and hit criteria that motivate subset seeds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the probability transducers B, DT1, DT2, and NT used in the seed-design experiments."}],"review_version":1}