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.
Get full access to this article
View all access options for this article.
References
1.
AhoA.V., and CorasickM.J.1975. Efficient string matching: An aid to bibliographic search. Commun. ACM, 18, 333–340.
2.
ApostolicoA., GuerraC., and PizziC.2014. Alignment free sequence similarity with bounded Hamming distance. In Proc. of the Data Compression Conf. (DCC), 183–192.
BassinoF., ClémentJ., FayolleJ., et al.2008. Constructions for clumps statistics. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. AI, 179–194.
5.
BattagliaG., CangelosiD., GrossiR., et al.2009. Masking patterns in sequences: A new class of motif discovery with don't cares. Theor. Comput. Sci., 410, 4327–4340.
6.
BensonG., and MakD.Y.2008. Exact distribution of a spaced seed statistic for DNA homology detection. In Proc. of the Int. Symp. on String Processing and Information Retrieval (SPIRE), 5280, 282–293.
7.
BodenM., SchöneichM., HorwegeS., et al.2013. Alignment-free sequence comparison with spaced k-mers. In Proc. of the German Conf. on Bioinformatics (GCB)34, 24–34.
8.
BrejováB., BrownD.G., and VinařT.2005. Vector seeds: An extension to spaced seeds. J. Comput. and Syst Sci., 70, 364–380.
9.
BřindaK.2014. Languages of lossless seeds. In Proc. of the Int. Conf. on Automata and Formal Languages (AFL)151, 139–150.
10.
BuhlerJ., KeichU., and SunY.2005. Designing seeds for similarity search in genomic DNA. J. Comput. and Syst. Sci., 70, 342–363.
11.
BurgeS.W., DaubJ., EberhardtR., et al.2012. Rfam 11.0: 10 years of RNA families. Nucleic Acids Res., 41, D226–D232.
12.
BurkhardtS., CrauserA., FerraginaP., et al.1999. q-gram based database searching using a suffix array (QUASAR). In Proc. of the Annu. Int. Conf. on Research in Computational Molecular Biology (RECOMB), 77–83.
13.
BurkhardtS., and KärkkäinenJ.2002. Better filtering with gapped q-grams. Fund. Inform., 56, 51–70.
14.
ChenY., SouaiaiaT., and ChenT.2009. PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds. Bioinformatics, 25, 2514–2521.
15.
ChorB., HornD., GoldmanN., et al.2009. Genomic DNA k-mer spectra: Models and modalities. Genome Biol., 10, R108.
16.
CominM., and VerzottoD.2012. Alignment-free phylogeny of whole genomes using underlying subwords. Algorithms Mol. Biol., 7, 34.
17.
CsűrösM.2004. Performing local similarity searches with variable length seeds. In Proc. of the 15th Annu. Combinatorial Pattern Matching Symp. (CPM)3109, 373–387.
18.
DavidM., DzambaM., ListerD., et al.2011. SHRiMP2: Sensitive yet practical short read mapping. Bioinformatics, 27, 1011–1012.
19.
DidierG., CorelE., LaprevotteI., et al.2012. Variable length local decoding and alignment-free sequence comparison. Theor. Comput. Sci., 462, 1–11.
20.
Do DucD., DinhH.Q., DangT.H., et al.2012. AcoSeeD: An ant colony optimization for finding optimal spaced seeds in biological sequence search. In Proc. of the 8th Int. Conf. on Swarm Intelligence (ANTS)7461, 204–211.
21.
EdgarR.C.2004. MUSCLE: Multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res., 32, 1792–1797.
22.
EgidiL., and ManziniG.2014a. Design and analysis of periodic multiple seeds. Theor. Comput. Sci., 522, 62–76.
23.
EgidiL., and ManziniG.2014b. Spaced seeds design using perfect rulers. Fund. Inform., 131, 187–203.
24.
Farach-ColtonM., LandauG.M., et al.2007. Optimal spaced seeds for faster approximate string matching. J. Comput. and Syst Sci., 73, 1035–1044.
25.
FrithM.C., and NoéL.2014. Improved search heuristics find 20,000 new alignments between human and mouse genomes. Nucleic Acids Res., 42, e59.
26.
GambinA., LasotaS., StartekM., et al.2011. Subset seed extension to Protein BLAST. In Proc. of the Int. Conf. on Bioinformatics Models, Methods and Algorithms, 149–158.
27.
GiladiE., HealyJ., MyersG., et al.2010. Error tolerant indexing and alignment of short reads with covering template families. J. Comput. Biol., 17, 1397–1411.
28.
GiraudM., SalsonM., DuezM., et al.2014. Fast multiclonal clusterization of V(D)J recombinations from high-throughput sequencing. BMC Genomics, 15, 409.
29.
HarrisR.S.2007. Improved pairwise alignment of genomic DNA. [Ph.D. thesis]. The Pennsylvania State University.
30.
HauboldB., PierstorffN., MöllerF., et al.2005. Genome comparison without alignment using shortest unique substrings. BMC Bioinformatics, 6, 123.
31.
HomerN., MerrimanB., and NelsonS.F.2009. BFAST: An alignment tool for large scale genome resequencing. PLoS One, 4, e7767.
32.
HopcroftJ.1971. An n log n algorithm for minimizing the states in a finite automaton, 189–196. In KohaviZ., and PazA., eds. The Theory of Machines and Computation. Academic Press, New York.
33.
HorwegeS., LindnerS., BodenM., et al.2014. Spaced words and kmacs: Fast alignment-free sequence comparison based on inexact word matches. Nucleic Acids Res., 42, W7–W11.
34.
HuangL.2006. Dynamic programming algorithms in semiring and hypergraph frameworks. Technical report. University of Pennsylvania. Philadelphia.
35.
IlieL., IlieS., and Mansouri BigvandA.2011. SpEED: fast computation of sensitive spaced seeds. Bioinformatics, 27, 2433–2434.
36.
IlieL., MohamadiH., Brian GoldingG., et al. 2013. BOND: Basic OligoNucleotide Design. BMC Bioinformatics, 14, 69.
37.
JoachimsT.2002. Learning to Classify Text using Support Vector Machines. Kluwer/Springer.
38.
KeichU., LiM., MaB., et al.2004. On spaced seeds for similarity search. Discrete Appl. Math., 138, 253–263.
39.
KiełbasaS.M., WanR., SatoK., et al.2011. Adaptive seeds tame genomic sequence comparison. Genome Res., 21, 487–493.
40.
KuangR., IeE., WangK., et al.2005. Profile-based string kernels for remote homology detection and motif extraction. J. Bioinform. Comput. Biol., 3, 527–550.
KucherovG., NoéL., and RoytbergM.A.2006. A unifying framework for seed sensitivity and its application to subset seeds. J. Bioinform. Comput. Biol., 4, 553–569.
43.
KucherovG., NoéL., and RoytbergM.A.2007. Subset seed automaton. In Proc. of the 12th Int. Conf. on Implementation and Application of Automata (CIAA)4783, 180–191.
LeimeisterC.-A., BodenM., HorwegeS., et al.2014. Fast alignment-free sequence comparison using spaced-word frequencies. Bioinformatics, 30, 1991–1999.
46.
LeslieC.S., EskinE., CohenA., et al.2004. Mismatch string kernels for discriminative protein classification. Bioinfomatics, 20, 467–476.
47.
LeslieC.S., EskinE., and Stafford NobleW.2002. The spectrum kernel: A string kernel for SVM protein classification. In Proc. of the Pacific Symp. on Biocomputing (PSB), 564–575.
48.
LiM., MaB., KismanD., et al.2004. PatternHunter II: Highly sensitive and fast homology search. J. Bioinform. Comput. Biol., 2, 417–439.
49.
LinH., ZhangZ., ZhangM.Q., et al.2008. ZOOM! Zillions Of Oligos Mapped. Bioinformatics, 24, 2431–2437.
50.
LiuZ., DeSantisT.Z., AndersenG.L., et al.2008. Accurate taxonomy assignments from 16S rRNA sequences produced by highly parallel pyrosequencers. Nucleic Acids Res., 36, e120.
51.
LodhiH., SaundersC., Shawe-TaylorJ., et al.2002. Text classification using string kernels. J. Mach. Learn. Res., 2, 419–444.
52.
MarschallT., HermsI., KaltenbachH.-M., et al.2012. Probabilistic arithmetic automata and their applications. IEEE/ACM Trans. Comput. Biol. Bioinf., 9, 1737–1750.
53.
MartinD.E.K.2013. Coverage of spaced seeds as a measure of clumping. In JSM Proc., Statistical Computing Section. American Statistical Association, Alexandria, Virginia.
54.
MartinD.E.K. and ColemanD.A.2011. Distribution of clump statistics for a collection of words. J. Appl. Probab., 48, 901–1204.
55.
MartinD.E.K., and NoéL.2014. Faster exact probabilities for statistics of overlapping pattern occurrences. Ann. Inst. Stat. Math. [Submitted]
56.
Maurer-StrohS., GunalanV., WongW.-C., et al.2013. A simple shortcut to unsupervised alignment-free phylogenetic genome groupings, even from unassembled sequencing reads. J. Bioinform. Comput. Biol., 11, 1343005.
57.
MichenerC.D., and SokalR.R.1957. A quantitative approach to a problem in classification. Evolution, 11, 130–162.
58.
MohriM.2009. Handbook of Weighted Automata, 213–254. Springer, New York.
59.
NicolasF., and RivalsÉ.2008. Hardness of optimal spaced seed design. J. Comput. and Syst Sci., 74, 831–849.
60.
NuelG.2008. Pattern Markov chains: optimal Markov chain embedding through deterministic finite automata. J. Appl. Probab., 45, 226–243.
61.
NuelG.2011. Bioinformatics - Trends and Methodologies, 173–194. InTech, Rijeka, Croatia.
OnoderaT., and ShibuyaT.2013. The gapped spectrum kernel for support vector machines. In Proc. of the Int. Conf. on Machine Learning and Data Mining in Pattern Recognition (MLDM)7988, 1–15.
64.
PinJ.-E.1998. Tropical semirings. In GunawardenaJ., ed. Idempotency, 11, Publ. Newton Inst., 50–69, Bristol. Cambridge University Press, Cambridge, UK.
65.
QiJ., LuoH., and HaoB.2004. CVTree: A phylogenetic tree reconstruction tool based on whole genomes. Nucleic Acids Res., 32, W45–W47.
66.
RasmussenK.R., StoyeJ., and MyersE.W.2006. Efficient q-gram filters for finding all ε-matches over a given length. J. Comput. Biol., 13, 296–308.
67.
RégnierM., FangB., and IakovishinaD.2014. Clump combinatorics, automata, and word asymptotics. In. Proc. of the Worksh. on Analytic Algorithmics and Combinatorics (ANALCO).
68.
SaigoH., VertJ.-P., UedaN., et al.2004. Protein homology detection using string alignment kernels. Bioinfomatics, 20, 1682–1689.
69.
SchenstedC.1961. Longest increasing and decreasing subsequences. Can. J. Math., 13, 179–191.
70.
SimonI.1988. Recognizable sets with multiplicities in the tropical semiring. In Mathematical Foundations of Computer Science, 324, 107–120.
71.
SimsaG.E., JunaS.-R., WuaG.A., et al.2009. Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions. Proc. Natl. Acad. Sci. USA., 106, 2677–2682.
72.
StefanovV.T., RobinS., and SchbathS.2007. Waiting times for clumps of patterns and for structured motifs in random sequences. Discrete Appl. Math., 155, 868–880.
73.
StropeaP.K., and MoriyamaE.N.2007. Simple alignment-free methods for protein classification: A case study from G-protein-coupled receptors. Genomics, 89, 602–612.
