{"id":"bc801fb5-ff13-470d-82c6-4273f771a38d","arxiv_id":"cs/0603106","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Seed detection probabilities are meaningfully higher on homogeneous alignments than on arbitrary alignments, and exact dynamic programming can compute these probabilities by counting culminating positive walks.","lead":"This paper studies how often DNA search tools that use short 'seed' patterns find a similarity, when the similarity must be a high-scoring region with no better-scoring subregion. It shows that testing seeds on all alignments, instead of only these high-scoring regions, underestimates their sensitivity, and provides exact counting and random generation algorithms for the new setting.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The bias claim rests on an unspecified distribution for 'general alignments'; without it, the reported underestimation may be an artifact of the uniform fixed-score model, not a property of real seed sensitivity.","rationale":"The paper's formal contribution, exact enumeration and dynamic programming for seed sensitivity under homogeneous alignments, appears sound: recurrences (5) and (6) correctly count culminating positive walks, and the hit-probability recursion is a natural extension of Keich et al.'s approach. The weak point is the inference from these exact computations to a general claim about bias in seed sensitivity estimation. The experiments define the comparison only qualitatively, and the general-alignment baseline is not specified. Without specifying that baseline, the reader cannot determine whether the reported gap is due to the importance of homogeneity or to an unrealistic uniform distribution over arbitrary fixed-score alignments. The paper's own Section 5 limits the uniform assumption, noting that local compositional properties would invalidate it. For the practical seed-design recommendation to be actionable, the comparison should be made against the Markov-model estimates that are standard in the seed-design literature, and ideally against empirical HSP distributions. This concern does not undermine the algorithms, but it does mean the central bias claim is conditionally established rather than fully demonstrated.","tokens_in":10748,"tokens_out":3888,"duration_ms":35839,"concrete_test":"Specify and implement the general-alignment baseline exactly (e.g., uniform over all binary strings of length n with score S), reproduce the four panels of Fig. 4, then recompute the same curves under a Bernoulli model with match probability q = (S/n + p)/(s + p), and under an empirical distribution of real HSPs obtained from a YASS or BLAST run on yeast chromosomes. If homogeneous hit probability no longer exceeds these realistic baselines by the reported margin, the underestimation claim is specific to the uniform fixed-score model and should be re-scoped.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 compares hit probabilities on homogeneous vs 'non-constrained' alignments of fixed score and length, but the general-alignment computation is only described as 'a simpler version ... details are left out.' The only fully specified distributions in the paper are uniform: the CPW counting combined with Lemma 2 gives uniform generation over fixed-score homogeneous sequences, and the natural counterpart is uniform over all binary strings of length n with total score S. Under those two distributions, the observed gap is a mathematical consequence of conditioning on homogeneity. That does not support the practical claim that 'measuring sensitivity on general alignments ... leads to an underestimation,' because standard sensitivity estimates (Buhler et al. 2003, Brejova et al. 2003, Choi & Zhang 2003) use Markov models of local composition, not uniform fixed-score alignments, and do not condition on exact total score. Section 5 itself concedes that the uniform equiprobability assumption 'would be no longer justified' once local compositional properties are considered. Thus the central bias claim is not validated against the models it nominally criticizes, nor against observed BLAST/Xdrop alignments. The YASS table is suggestive but lacks threshold and statistical detail. The algorithmic contribution stands, but the headline bias result lacks a specified, realistic baseline.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses estimation of seed sensitivity for seed-based similarity search. Its object of study is the homogeneous alignment (a gapless alignment whose total score exceeds the score of every proper subalignment), modeled as a culminating positive walk (CPW). The authors give recurrences for counting CPWs of fixed length with arbitrary or fixed total score (Lemmas 4-6), a uniform random-generation scheme based on Lemma 2, and a dynamic program for the exact probability that a seed detects a uniformly random homogeneous sequence of given length and score, with an extension to multi-seed strategies. They then use these tools to argue that sensitivity measured on arbitrary alignments underestimates sensitivity on homogeneous alignments (Section 4, Fig. 4), that the optimal seed can differ between the two models (Table 1), and, via YASS experiments on yeast chromosomes (Table 2), that seeds tuned on homogeneous alignments find more high-scoring alignments. Section 5 acknowledges that the uniform equiprobability assumption underlying the model is not justified for alignments with local compositional properties.","tokens_in":11010,"tokens_out":26815,"duration_ms":235822,"significance":"If the results hold, the paper's algorithmic contribution is substantial and self-contained: the CPW counting recurrences (Lemmas 4-6) give a parameter-free way to count and uniformly generate homogeneous alignments, the random-generation scheme realizes Lemma 2 with O(n) per-sample cost after O(n^3) or O(S·n) preprocessing, and the DP in Section 3 extends exact sensitivity computation to a broad class of seed strategies on homogeneous alignments. These are concrete, checkable contributions, and the model-level prediction (conditioning on homogeneity raises hit probability under the uniform fixed-score distribution) is falsifiable and demonstrated in Fig. 4. The limitation is that the practical significance rests on the uniform equiprobability assumption, which the authors concede is not justified for compositionally heterogeneous alignments, and the experimental baseline for 'arbitrary alignments' is not fully specified. Scoped as an exact model-based analysis with a properly framed bias claim, the paper is a worthwhile methodological contribution to seed design.","major_comments":[{"comment":"The probabilities for 'arbitrary alignments' are said to be computed by 'a simpler version of the algorithm ... (details are left out).' The paper's central claim, that measuring sensitivity on general alignments leads to an underestimation, is quantified entirely against this unspecified model. Different choices of the general-alignment distribution (uniform over fixed-score strings, Bernoulli with a match probability, or a Markov model) can change both the size and the direction of the gap, so the reported bias is neither reproducible nor attributable to the homogeneity condition as such. Please specify the exact baseline distribution and algorithm, and report the baseline probabilities in a way that allows independent verification.","section":"Section 4, Fig. 4 and Table 1"},{"comment":"The Introduction states that measuring sensitivity on 'general alignments instead of homogeneous alignments' leads to an underestimation of sensitivity, but Section 5 concedes that the uniform equiprobability assumption used here 'would be no longer justified' once local compositional properties of alignments are taken into account. The sensitivity estimators this paper sets out against ([6], [3], [10]) are Markov-model based and do not condition on exact total score, so the comparison in Fig. 4 does not test the claim against the standard baselines it criticizes. Either the bias claim should be explicitly scoped to the uniform fixed-score model, or the paper should add a comparison against Markov-model and observed-alignment baselines.","section":"Introduction vs. Section 5"},{"comment":"The listed seed 111011101001111 is reported with Ph=0.975462 and Pa=0.993076, i.e., its hit probability on arbitrary alignments exceeds that on homogeneous alignments, the opposite direction of the bias shown in Fig. 4. This parameter set also lists only one seed rather than a paired π_h/π_a row, and the caption ('π{h|a}') does not state which rows are which. Please clarify the table structure and discuss whether the underestimation bias reverses for weight-11 seeds at this length/score; the Introduction's unqualified claim appears too strong otherwise.","section":"Table 1, row (40,20), w=11"},{"comment":"The recursion for P(i,M,y) is the core of the exact algorithm, but the transition probabilities P1 and P0 in (7) are introduced through a 'flip over the whole picture' argument that is not written out: the identity relating the number of compatible completions to |D^S_{S-y,i}| is asserted, and the index convention for i is not fully specified in the text. Because the exactness of the hit-probability computation is the paper's main algorithmic deliverable, a formal derivation of (7) and a correctness statement for the recursion would be needed to verify the claim.","section":"Section 3, conditions (iii)-(vi) and eq. (7)"},{"comment":"The YASS experiments report raw counts of high-scoring alignments with no stated score threshold, no measure of variability, and no statistical comparison; in the IX row the two seeds tie exactly (519 vs 519). Without specifying the threshold used to define 'high-scoring' and providing a statistical test (e.g., a paired comparison over the six chromosome sets), the conclusion that the homogeneous-optimized seed 'allows to identify more relevant similarities' is not supported.","section":"Section 4, Table 2"}],"minor_comments":[{"comment":"The displayed telescoping product contains a stray 's' in 'Pα_n(α1α2sαn−1)'; the last factor should read Pα_n(α1α2⋯αn−1).","section":"Lemma 2, eq. (2)"},{"comment":"The condition 'y ≤ 0 and n > 0' appears to be intended as 'y ≤ 0 and i > 0', since the empty prefix (i=0, y=0) is a valid starting state; as written, condition (iii) would reject every starting state.","section":"Section 3, condition (iii)"},{"comment":"The phrase 'at least two times less' is ambiguous; the intended meaning is presumably that the missed fraction on homogeneous alignments is at most half of that on arbitrary alignments.","section":"Section 4"},{"comment":"The equivalence between homogeneity and the CPW conditions is asserted without proof; a brief justification (e.g., noting that every proper segment's score lies between two prefix scores) would help readers.","section":"Section 2"},{"comment":"For the +1/−3 scoring, sequences of length n and score S exist only when n satisfies the implied Diophantine constraint (e.g., for S=16, n must be a multiple of 4); the axes and the text should state this.","section":"Fig. 4"}],"recommendation":"major_revision","confidential_remarks":"The algorithmic core is sound and worth publishing, but the headline claim (a practical underestimation bias) is the weakest part and needs either a specified baseline plus a Markov-model comparison, or an explicit scoping to the uniform model. I would not accept the current version because the experiments are not reproducible as written; likewise I would not reject, since the counting and hit-probability algorithms are genuine contributions and the bias issue is fixable within scope. No concerns about novelty disclosure; the relationship to [15,3,6] is acknowledged. A code or data appendix for the baseline computation would materially help referees and readers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The honest bottom line: the algorithmic core is real, the headline bias claim is under-supported. The paper gives a clean characterization of homogeneous alignments as culminating positive walks, and from that an exact dynamic program for seed sensitivity under the uniform fixed-score model, plus a random generation algorithm. That part is solid. The recurrences are coherent, the O(n^3) counting and O(S·n) fixed-score versions check out, and the extension to multiple seeds is a natural and useful step. I would trust this as a new tool for a well-defined probability model. The soft spot is exactly where the stress test points. Section 4 compares against arbitrary alignments computed with a simpler version of the algorithm, with details left out. That is a serious gap because the paper's motivation is that measuring on arbitrary alignments underestimates sensitivity. Without a specified distribution for arbitrary alignments, the gap in Figure 4 and Table 1 is not a fully measurable claim. If the natural baseline is uniform over all fixed-score binary strings, then conditioning on homogeneity necessarily changes the distribution, so the gap is not surprising and does not transfer to realistic settings. The authors themselves concede in Section 5 that uniform equiprobability is no longer justified once local compositional properties matter. So the practical conclusion that seed design should be done on homogeneous alignments is asserted, not demonstrated by these experiments. The YASS chromosome counts are suggestive but lack thresholds and statistical detail. One more thing: the contrast with Markov-model approaches is fair up to a point, but those models do not condition on exact score; they estimate sensitivity given local composition. So the bias claim as stated does not directly land on Buhler, Brejova, or Choi-Zhang. The paper's contribution is better framed as: here is an exact sensitivity computation for a different, globally constrained model. Who is this for? Researchers working on spaced seed design and sensitivity estimation. They will get a new exact algorithm and a useful warning that the uniform model is limited. It deserves serious peer review, but the bias claim needs to be reframed as conditional on the uniform fixed-score model, and the arbitrary baseline must be specified or the experiments redone against realistic models.","headline":"A genuinely useful algorithmic contribution for computing seed sensitivity on homogeneous alignments, but the headline practical bias claim rests on an unspecified baseline and an unvalidated uniformity assumption.","tokens_in":703,"tokens_out":1601,"would_cite":true,"duration_ms":27118,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Seed sensitivity in similarity search is systematically underestimated when tested on arbitrary alignments, and exact hit probabilities on homogeneous alignments can be computed for a broad class of seed strategies.","keywords":["seed sensitivity","homogeneous alignments","maximal scoring segments","spaced seeds","hit probability","random generation","dynamic programming","culminating positive walks"],"falsifier":"Fix a common match/mismatch scoring system such as +1/-3 and a seed; collect many real maximal scoring segments of fixed length $n$ and score $S$ from genomic comparisons. Count the fraction that contain the seed and compare it with the algorithm's predicted probability on uniformly random homogeneous alignments. A systematic, composition-dependent discrepancy would falsify the uniform model and show that the sensitivity estimates need reweighting.","tokens_in":10589,"feed_emoji":"🧬","tokens_out":9517,"duration_ms":82656,"temperature":0.7,"pith_summary":"Similarity-search programs are meant to find maximal scoring segments: gapless alignments whose score is strictly higher than any proper contiguous subsegment. The paper's central claim is that seed sensitivity should therefore be measured on those homogeneous alignments, not on arbitrary alignments, and that measuring otherwise introduces a systematic bias toward underestimation. The paper provides an exact dynamic programming algorithm for the probability that a seed detects a random homogeneous alignment, covering contiguous and spaced seeds as well as single, double, and multiple-seed strategies. It also gives a uniform random generation procedure for homogeneous alignments, and experiments show that optimal seeds chosen under the two models can differ.","feed_headline":"Homogeneous alignments fix a bias in seed sensitivity","feed_subtitle":"Computing seed detection rates on the alignments search tools actually return changes which seeds win.","key_machinery":"The central object is the culminating positive walk (CPW): a lattice path made of steps $(1, +s)$ and $(1, -p)$ that starts at $(0,0)$, ends at $(n,S)$, stays strictly above zero, and stays strictly below $S$ before the final step. A match/mismatch alignment is homogeneous exactly when its score walk is a CPW, so counting CPWs counts homogeneous alignments. The walk representation is what carries the argument: it converts the global homogeneity condition into a local positivity condition, allowing suffix-counting recurrences to generate homogeneous alignments uniformly and to weigh each extension in the sensitivity dynamic program.","core_discovery":"The discovery is that requiring an alignment to be homogeneous changes the probability that a seed detects it, and the change can be computed exactly. On the match/mismatch model with match score $s$ and mismatch score $-p$, a binary alignment is homogeneous exactly when its score walk stays strictly positive and strictly below the final score until the end; these culminating positive walks are counted by disjoint-union recurrences. From those counts, the paper derives an exact recurrence for hit probability, parameterized by seed span and weight, whose output differs from the unconstrained model: in the reported experiments the fraction of homogeneous alignments missed is at least two times smaller than the miss rate estimated on arbitrary alignments, and the highest-scoring seed of a given weight can be different. The authors present this as a correction, not a replacement: Markov-model approaches impose local composition while the homogeneous model imposes global constraints, and both would ideally be combined.","pith_inferences":["If real high-scoring segment pairs carry nonuniform match/mismatch patterns, the uniform equiprobability model could be replaced by composition-dependent weights inside the same walk recurrences; testing this would require estimating conditional pattern distributions from actual alignments.","Because CPWs are a standard lattice-path family, asymptotic or transfer-matrix methods might yield closed-form approximations for hit probability at large $n$, making seed optimization over long alignments practical without full dynamic programming.","Re-running previously published spaced-seed optimizations under the homogeneity constraint could change which seeds are recommended, since the bias is large enough to flip optimal-seed tables."],"forward_implications":["Seed sensitivity and seed optimization should be recomputed over homogeneous alignments; the paper gives concrete parameter settings where the optimal seed changes.","Estimates based on arbitrary alignments understate detection power, so seed rankings from those estimates may be unreliable for the alignments search programs actually return.","The exact algorithm extends to multi-seed strategies with constraints on seed overlap and distance, covering most seed designs used in current similarity search.","Uniform random generation of homogeneous alignments offers an experimental way to evaluate seed strategies that are too complex for the exact computation.","The counting machinery transfers to the study of high-scoring segments in single protein sequences, where homogeneous and maximal scoring segments are biologically meaningful."],"supporting_citations":[{"why":"Defines maximal scoring segments, the formalization of homogeneous alignments that motivates measuring sensitivity on them.","marker":"[21]"},{"why":"Contributes the dynamic-programming scheme for single-seed hit probability that Section 3 extends to homogeneous alignments.","marker":"[15]"},{"why":"Provides the Markov-model framework and multiple-seed extension whose estimates the paper contrasts with the homogeneous approach.","marker":"[6]"},{"why":"Supplies the HMM-based spaced-seed sensitivity algorithm that this paper complements and compares against.","marker":"[3]"},{"why":"Provides the suffix-counting method used to generate homogeneous sequences uniformly at random.","marker":"[24]"},{"why":"Introduces spaced seeds and the specific seed used in the experimental comparison.","marker":"[18]"}],"fun_headline_variants":["Seed sensitivity shifts when alignments go homogeneous","Homogeneous alignments correct seed hit bias","Exact seed hits need homogeneous alignments","Why seed ranks change on homogeneous alignments","Homogeneous alignments halve seed misses"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything in the numerical comparisons rests on the assumption that all homogeneous alignments with a given length and total score are equally likely; the paper itself notes this becomes unjustified once local compositional properties of alignments are taken into account.","fun_headline_variants_meta":{"raw":{"variants":["Seed sensitivity shifts when alignments go homogeneous","Homogeneous alignments correct seed hit bias","Exact seed hits need homogeneous alignments","Why seed ranks change on homogeneous alignments","Homogeneous alignments halve seed misses"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000538,"raw_usage":{"total_tokens":2498,"prompt_tokens":780,"completion_tokens":1718,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":396,"completion_tokens_details":{"reasoning_tokens":1652}},"tokens_in":396,"tokens_out":1718,"duration_ms":13341,"temperature":1.0,"reasoning_tokens":1652,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-28T18:08:06.071817+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a common match/mismatch scoring system such as +1/-3 and a seed; collect many real maximal scoring segments of fixed length $n$ and score $S$ from genomic comparisons. Count the fraction that contain the seed and compare it with the algorithm's predicted probability on uniformly random homogeneous alignments. A systematic, composition-dependent discrepancy would falsify the uniform model and show that the sensitivity estimates need reweighting.","supporting_citations":[{"cited_title":"Brejova, D","cited_arxiv_id":null,"evidence_quote":"Supplies the HMM-based spaced-seed sensitivity algorithm that this paper complements and compares against."},{"cited_title":"Ruzzo and M","cited_arxiv_id":null,"evidence_quote":"Defines maximal scoring segments, the formalization of homogeneous alignments that motivates measuring sensitivity on them."},{"cited_title":"Keich, M","cited_arxiv_id":null,"evidence_quote":"Contributes the dynamic-programming scheme for single-seed hit probability that Section 3 extends to homogeneous alignments."},{"cited_title":"Buhler, U","cited_arxiv_id":null,"evidence_quote":"Provides the Markov-model framework and multiple-seed extension whose estimates the paper contrasts with the homogeneous approach."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the suffix-counting method used to generate homogeneous sequences uniformly at random."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces spaced seeds and the specific seed used in the experimental comparison."}],"review_version":1}