A coverage criterion for spaced seeds and its applications to support vector machine string kernels and k-mer distances.
Spaced seeds have been recently shown to not only detect more alignments, but also to give a more accurate measure of phylogenetic distances, and to provide a lower misclassification rate when used with Support Vector Machines (SVMs). We confirm by independent experiments these two results, and propose in this article to use a coverage criterion to measure the seed efficiency in both cases in order to design better seed patterns. We show first how this coverage criterion can be directly measured by a full automaton-based approach. We then illustrate how this criterion performs when compared with two other criteria frequently used, namely the single-hit and multiple-hit criteria, through correlation coefficients with the correct classification/the true distance. At the end, for alignment-free distances, we propose an extension by adopting the coverage criterion, show how it performs, and indicate how it can be efficiently computed.
1 Laboratoire d'Informatique Fondamentale de Lille (LIFL) (UMR 8022 Lille 1/CNRS) - Inria Lille, Villeneuve d'Ascq, France .
Laurent
L
Noé
Donald E K
DE
Martin
D000465:Algorithms; D006801:Humans; D010363:Pattern Recognition, Automated; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein; D017386:Sequence Homology, Amino Acid; D012984:Software; D060388:Support Vector Machine
alignment-free distance; coverage; spaced seeds; support vector machine