@InCollection{SonRaeRie07,
	author =       {S\"oren Sonnenburg and Gunnar R{\"a}tsch and Konrad Rieck},
	title =        {Large Scale Learning with String Kernels},
	booktitle =    {Large Scale Kernel Machines},
	publisher = {MIT Press},
	year =     {2007},
	editor = {Bottou, L\'{e}on and Chapelle, Olivier and {DeCoste}, Dennis and Weston, Jason},
	address = {Cambridge, MA.},
    pages = {73--103},
	pdf =  {http://sonnenburgs.de/soeren/publications/SonRaeRie07.pdf},
	abstract = { In genomic sequence analysis tasks like splice site recognition or promoter identification, large amounts of training sequences are available, and indeed needed to achieve sufficiently high classification performances. In this chapter we study string kernels that can be computed in linear time w.r.t. the length of the input sequences. In particular the recently proposed Spectrum kernel, the Weighted Degree kernel (WD) and the Weighted Degree kernel with shifts, which have been successfully used for various sequence analysis tasks.  We discuss extensions using data structures such as tries and suffix trees as well as modifications of a SVM chunking algorithm in order to significantly accelerate SVM training and their evaluation on test sequences. Our simulations using the WD kernel and Spectrum kernel show that large scale SVM training can be accelerated by factors of 7 and 60 times, respectively, while requiring considerably less memory.  We demonstrate that these algorithms can be effectively parallelized for further acceleration.  Our method allows us to train SVMs on sets as large as 10 million sequences and solve Multiple Kernel Learning problems with 1 million sequences.  Moreover, using these techniques the evaluation on new sequences is often several thousand times faster, allowing us to apply the classifiers on genome-sized data sets with seven billion test examples. We finally demonstrate how the proposed data structures can be used to understand the SVM classifiers decision function. All presented algorithms are implemented in our Machine Learning toolbox \texttt{SHOGUN} for which the source code is publicly available at \url{http://www.fml.tuebingen.mpg.de/raetsch/projects/shogun}.}

}