REVIEW
A unifying framework for seed sensitivity and its application to subset seeds (Extended abstract)
Other Computer Science · Submitted 27 Mar 2006 · 23 references
Pith's verdict: 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.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
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.
The reading
What carries the argument
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Original abstract
We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem - a set of target alignments, an associated probability distribution, and a seed model - that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.
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.
The abstract, sentence by sentence
We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem - a set of target alignments, an associated probability distribution, and a seed model - that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. | contribution 1.00 | 0.90 | 0.16 | asserted 0.95 |
| s1 | It treats separately three components of the seed sensitivity problem - a set of target alignments, an associated probability distribution, and a seed model - that are specified by distinct finite automata. | method 0.98 | 0.67 | 0.05 | asserted 1.00 |
| s2 | The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. | contribution 0.87 | 0.93 | 0.09 | asserted 1.00 |
| s3 | Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds. | result 0.99 | 0.95 | 0.75 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:cs/0603105 by the authors.
References
How the literature uses it
Papers whose main result relates to this one's
States the same result 1 paper
-
Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.
A unifying framework for seed sensitivity and its application to subset seeds · 1.00
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.