Estimating seed sensitivity on homogeneous alignments

Gregory Kucherov (LIFL); Laurent Noe (LIFL); Yann Ponty (LRI)

REVIEW

Estimating seed sensitivity on homogeneous alignments

Gregory Kucherov (LIFL), Laurent Noe (LIFL), Yann Ponty (LRI)

Other Computer Science · Submitted 27 Mar 2006 · 26 references

Pith's verdict: 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.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 5 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDcs/0603106 (version 1)

Pith IDQCSBMNYQ, Pith's permanent record of this paper and its review

CitationGregory Kucherov (LIFL), Laurent Noe (LIFL), Yann Ponty (LRI). "Estimating seed sensitivity on homogeneous alignments." arXiv:cs/0603106 (2006). https://pith.science/paper/QCSBMNYQ

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the 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.

Referee report

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 objections (5)

[Section 4, Fig. 4 and Table 1] 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.
[Introduction vs. Section 5] 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.
[Table 1, row (40,20), w=11] 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 3, conditions (iii)-(vi) and eq. (7)] 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 4, Table 2] 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.

Minor objections (5)

[Lemma 2, eq. (2)] 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 3, condition (iii)] 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 4] 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 2] 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.
[Fig. 4] 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.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

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.

The reading

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.

What carries the argument

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.

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Original abstract

We address the problem of estimating the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,526 input tokens, $0.0001 reported.

What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.22 · human participants 0.02 · controlled comparison 0.26 · randomized assignment 0.02 · states quantitative result 0.08 · compares with prior results 0.85 · mentions code or data availability 0.03.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We address the problem of estimating the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We address the problem of estimating the sensitivity of seed-based similarity search algorithms.	background 0.74	0.66	0.05	asserted 0.69
s1	In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments.	contribution 0.69	0.62	0.07	asserted 0.98
s2	We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies.	method 0.70	0.96	0.11	asserted 1.00
s3	We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.	result 0.98	0.94	0.47	asserted 1.00

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from simulation or computation 0.81.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** An alignment uniquely associated with a walk.

**Figure 2.** Suffixes B associated to a prefix A of Cn depend only of the maximal ordinate h and current ordinate y In general, one has to precompute up to |Σ| n values Pα(wp). However, in the case of homogeneous sequences,

**Figure 3.** Computing the seed detection probability on ho

**Figure 4.** Seed detection probability on homogeneous vs arbi

Figures reproduced from arXiv:cs/0603106 by the authors.

References

Works cited (26)

[6]

J. Buhler, U. Keich, and Y . Sun. Designing seeds for sim- ilarity search in genomic DNA. In Proceedings of the 7th Annual International Conference on Computational Molec- ular Biology (RECOMB), Berlin (Germany) , pages 67–75. ACM Press, April 2003

View on Pith 2003
[3]

B. Brejova, D. Brown, and T. Vinar. Optimal spaced seeds for Hidden Markov Models, with application to homologous coding regions. In M. C. R. Baeza-Yates, E. Chavez, edi- tor, Proceedings of the 14th Symposium on Combinatorial Pattern Matching, Morelia (Mexico) , volume 2676 of Lec- ture Notes in Computer Science, pages 42–54. Springer, June 2003

View on Pith 2003
[10]

K. Choi and L. Zhang. Sensitivity analysis and efﬁcient method for identifying optimal spaced seeds. Journal of Computer and System Sciences, 2003. to appear

View on Pith 2003
[1]

S. Altschul, W. Gish, W. Miller, E. Myers, and D. Lipman. Basic Local Alignment Search Tool. Journal of Molecular Biology, 215:403–410, 1990

View on Pith 1990
[2]

S. Altschul, T. Madden, A. Sch¨ affer, J. Zhang, Z. Zhang, W. Miller, and D. Lipman. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nu- cleic Acids Research, 25(17):3389–3402, 1997

View on Pith 1997
[4]

B. Brejova, D. Brown, and T. Vinar. Vector seeds: an ex- tension to spaced seeds allows substantial improvements in sensitivity and speciﬁcity. In R. P. G. Benson, editor, Pro- ceedings of the 3rd International Workshop in Algorithms in Bioinformatics (WABI), Budapest (Hungary) , volume 2812 of Lecture Notes in Computer Science. Springer, September 2003

View on Pith 2003
[5]

J. Buhler. Efﬁcient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics, 17(5):419–428, 2001

View on Pith 2001
[7]

S. Burkhardt and J. K¨ arkk¨ ainen. Better ﬁltering with gapped q-grams. Fundamenta Informaticae, 56(1-2):51–70,

View on Pith
[8]

A. Califano and I. Rigoutsos. Flash: A fast look-up algo- rithm for string homology. In Proceedings of the 1st Inter- national Conference on Intelligent Systems for Molecular Bi- ology (ISMB), pages 56–64, July 1993

View on Pith 1993
[9]

K. Choi, F. Zeng, and L. Zhang. Good spaced seeds for ho- mology search. Bioinformatics, 2003. accepted

View on Pith 2003
[11]

A. Denise. G´ en´ eration al´ eatoire et uniforme de mots de langages rationnels (Uniform random generation of words of regular languages). Theoretical Computer Science , 159(1):43–63, 1996

View on Pith 1996
[12]

T. Hickey and J. Cohen. Uniform random generation of strings in a context-free language. SIAM. J. Comput , 12(4):645–655, 1983

View on Pith 1983
[13]

S. Karlin and S. Altschul. Applications and statistics for mul- tiple high-scoring segments in molecular sequences. Proc Natl Acad Sci USA, 90(12):5873–5877, June 15 1993

View on Pith 1993
[14]

S. Karlin and V . Brendel. Chance and signiﬁcance in protein and DNA sequence analysis. Science, 257:39–49, 1992

View on Pith 1992
[15]

U. Keich, M. Li, B. Ma, and J. Tromp. On spaced seeds for similarity search. to appear in Discrete Applied Mathemat- ics, 2002

View on Pith 2002
[16]

W. J. Kent. BLAT–the BLAST-like alignment tool. Genome Research, 12:656–664, 2002

View on Pith 2002
[17]

D. Lipman and W. Pearson. Improved tools for biological sequence comparison. Proc. Natl. Acad. Sci. USA, 85:2444– 2448, 1988

View on Pith 1988
[18]

B. Ma, J. Tromp, and M. Li. PatternHunter: Faster and mor e sensitive homology search. Bioinformatics, 18(3):440–445, 2002

View on Pith 2002
[19]

L. No´ e and G. Kucherov. Y ASS: Similarity search in DNA sequences. Research Report RR-4852, INRIA, Jun 2003

View on Pith 2003
[20]

P. Pevzner and M. Waterman. Multiple ﬁltration and ap- proximate pattern matching. Algorithmica, 13:135–154,

View on Pith
[21]

W. Ruzzo and M. Tompa. A linear time algorithm for ﬁnd- ing all maximal scoring subsequences. In Seventh Interna- tional Conference on Intelligent Systems for Molecular Biol- ogy (ISMB), pages 234–241, Heidelberg (Germany), 1999

View on Pith 1999
[22]

S. Schwartz, J. Kent, A. Smit, Z. Zhang, R. Baertsch, R. Hardison, D. Haussler, and W. Miller. Human–mouse alignments with BLASTZ. Genome Research, 13:103–107, 2003

View on Pith 2003
[23]

T. Smith and M. Waterman. Identiﬁcation of common molec- ular subsequences. Journal of Molecular Biology, 147(195– 197), March 1981

View on Pith 1981
[24]

H. Wilf. A uniﬁed setting for sequencing, ranking, and s e- lection algorithms for combinatorial objects. Advances in Mathematics, 24:281–291, 1977

View on Pith 1977
[1995]

Preliminary version in Combinatorial Pattern Match- ing 1993

View on Pith 1993
[2003]

Preliminary version in Combinatorial Pattern Match- ing 2001

View on Pith 2001

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [6]

J. Buhler, U. Keich, and Y . Sun. Designing seeds for sim- ilarity search in genomic DNA. In Proceedings of the 7th Annual International Conference on Computational Molec- ular Biology (RECOMB), Berlin (Germany) , pages 67–75. ACM Press, April 2003

View on Pith 2003

[2] [3]

B. Brejova, D. Brown, and T. Vinar. Optimal spaced seeds for Hidden Markov Models, with application to homologous coding regions. In M. C. R. Baeza-Yates, E. Chavez, edi- tor, Proceedings of the 14th Symposium on Combinatorial Pattern Matching, Morelia (Mexico) , volume 2676 of Lec- ture Notes in Computer Science, pages 42–54. Springer, June 2003

View on Pith 2003

[3] [10]

K. Choi and L. Zhang. Sensitivity analysis and efﬁcient method for identifying optimal spaced seeds. Journal of Computer and System Sciences, 2003. to appear

View on Pith 2003

[4] [1]

S. Altschul, W. Gish, W. Miller, E. Myers, and D. Lipman. Basic Local Alignment Search Tool. Journal of Molecular Biology, 215:403–410, 1990

View on Pith 1990

[5] [2]

S. Altschul, T. Madden, A. Sch¨ affer, J. Zhang, Z. Zhang, W. Miller, and D. Lipman. Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nu- cleic Acids Research, 25(17):3389–3402, 1997

View on Pith 1997

[6] [4]

B. Brejova, D. Brown, and T. Vinar. Vector seeds: an ex- tension to spaced seeds allows substantial improvements in sensitivity and speciﬁcity. In R. P. G. Benson, editor, Pro- ceedings of the 3rd International Workshop in Algorithms in Bioinformatics (WABI), Budapest (Hungary) , volume 2812 of Lecture Notes in Computer Science. Springer, September 2003

View on Pith 2003

[7] [5]

J. Buhler. Efﬁcient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics, 17(5):419–428, 2001

View on Pith 2001

[8] [7]

S. Burkhardt and J. K¨ arkk¨ ainen. Better ﬁltering with gapped q-grams. Fundamenta Informaticae, 56(1-2):51–70,

View on Pith

[9] [8]

A. Califano and I. Rigoutsos. Flash: A fast look-up algo- rithm for string homology. In Proceedings of the 1st Inter- national Conference on Intelligent Systems for Molecular Bi- ology (ISMB), pages 56–64, July 1993

View on Pith 1993

[10] [9]

K. Choi, F. Zeng, and L. Zhang. Good spaced seeds for ho- mology search. Bioinformatics, 2003. accepted

View on Pith 2003

[11] [11]

A. Denise. G´ en´ eration al´ eatoire et uniforme de mots de langages rationnels (Uniform random generation of words of regular languages). Theoretical Computer Science , 159(1):43–63, 1996

View on Pith 1996

[12] [12]

T. Hickey and J. Cohen. Uniform random generation of strings in a context-free language. SIAM. J. Comput , 12(4):645–655, 1983

View on Pith 1983

[13] [13]

S. Karlin and S. Altschul. Applications and statistics for mul- tiple high-scoring segments in molecular sequences. Proc Natl Acad Sci USA, 90(12):5873–5877, June 15 1993

View on Pith 1993

[14] [14]

S. Karlin and V . Brendel. Chance and signiﬁcance in protein and DNA sequence analysis. Science, 257:39–49, 1992

View on Pith 1992

[15] [15]

U. Keich, M. Li, B. Ma, and J. Tromp. On spaced seeds for similarity search. to appear in Discrete Applied Mathemat- ics, 2002

View on Pith 2002

[16] [16]

W. J. Kent. BLAT–the BLAST-like alignment tool. Genome Research, 12:656–664, 2002

View on Pith 2002

[17] [17]

D. Lipman and W. Pearson. Improved tools for biological sequence comparison. Proc. Natl. Acad. Sci. USA, 85:2444– 2448, 1988

View on Pith 1988

[18] [18]

B. Ma, J. Tromp, and M. Li. PatternHunter: Faster and mor e sensitive homology search. Bioinformatics, 18(3):440–445, 2002

View on Pith 2002

[19] [19]

L. No´ e and G. Kucherov. Y ASS: Similarity search in DNA sequences. Research Report RR-4852, INRIA, Jun 2003

View on Pith 2003

[20] [20]

P. Pevzner and M. Waterman. Multiple ﬁltration and ap- proximate pattern matching. Algorithmica, 13:135–154,

View on Pith

[21] [21]

W. Ruzzo and M. Tompa. A linear time algorithm for ﬁnd- ing all maximal scoring subsequences. In Seventh Interna- tional Conference on Intelligent Systems for Molecular Biol- ogy (ISMB), pages 234–241, Heidelberg (Germany), 1999

View on Pith 1999

[22] [22]

S. Schwartz, J. Kent, A. Smit, Z. Zhang, R. Baertsch, R. Hardison, D. Haussler, and W. Miller. Human–mouse alignments with BLASTZ. Genome Research, 13:103–107, 2003

View on Pith 2003

[23] [23]

T. Smith and M. Waterman. Identiﬁcation of common molec- ular subsequences. Journal of Molecular Biology, 147(195– 197), March 1981

View on Pith 1981

[24] [24]

H. Wilf. A uniﬁed setting for sequencing, ranking, and s e- lection algorithms for combinatorial objects. Advances in Mathematics, 24:281–291, 1977

View on Pith 1977

[25] [1995]

Preliminary version in Combinatorial Pattern Match- ing 1993

View on Pith 1993

[26] [2003]

Preliminary version in Combinatorial Pattern Match- ing 2001

View on Pith 2001