Links to Exploration step
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">String kernels for protein sequence comparisons: improved fold recognition</title>
<author><name sortKey="Nojoomi, Saghi" sort="Nojoomi, Saghi" uniqKey="Nojoomi S" first="Saghi" last="Nojoomi">Saghi Nojoomi</name>
<affiliation><nlm:aff id="Aff1">Biotechnology program, University of California, Davis, 1, Shields Avenue, Davis, CA, 95616 USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Koehl, Patrice" sort="Koehl, Patrice" uniqKey="Koehl P" first="Patrice" last="Koehl">Patrice Koehl</name>
<affiliation><nlm:aff id="Aff2">Department of Computer Science and Genome Center, 1, Shields Avenue, Davis, CA, 95616 USA</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">28245816</idno>
<idno type="pmc">5331664</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5331664</idno>
<idno type="RBID">PMC:5331664</idno>
<idno type="doi">10.1186/s12859-017-1560-9</idno>
<date when="2017">2017</date>
<idno type="wicri:Area/Pmc/Corpus">000264</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000264</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">String kernels for protein sequence comparisons: improved fold recognition</title>
<author><name sortKey="Nojoomi, Saghi" sort="Nojoomi, Saghi" uniqKey="Nojoomi S" first="Saghi" last="Nojoomi">Saghi Nojoomi</name>
<affiliation><nlm:aff id="Aff1">Biotechnology program, University of California, Davis, 1, Shields Avenue, Davis, CA, 95616 USA</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Koehl, Patrice" sort="Koehl, Patrice" uniqKey="Koehl P" first="Patrice" last="Koehl">Patrice Koehl</name>
<affiliation><nlm:aff id="Aff2">Department of Computer Science and Genome Center, 1, Shields Avenue, Davis, CA, 95616 USA</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2017">2017</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>The amino acid sequence of a protein is the blueprint from which its structure and ultimately function can be derived. Therefore, sequence comparison methods remain essential for the determination of similarity between proteins. Traditional approaches for comparing two protein sequences begin with strings of letters (amino acids) that represent the sequences, before generating textual alignments between these strings and providing scores for each alignment. When the similitude between the two protein sequences to be compared is low however, the quality of the corresponding sequence alignment is usually poor, leading to poor performance for the recognition of similarity.</p>
</sec>
<sec><title>Results</title>
<p>In this study, we develop an alignment free alternative to these methods that is based on the concept of string kernels. Starting from recently proposed kernels on the discrete space of protein sequences (Shen et al, <italic>Found. Comput. Math.</italic>
, 2013,14:951-984), we introduce our own version, SeqKernel. Its implementation depends on two parameters, a coefficient that tunes the substitution matrix and the maximum length of <italic>k-mers</italic>
that it includes. We provide an exhaustive analysis of the impacts of these two parameters on the performance of SeqKernel for fold recognition. We show that with the right choice of parameters, use of the SeqKernel similarity measure improves fold recognition compared to the use of traditional alignment-based methods. We illustrate the application of SeqKernel to inferring phylogeny on RNA polymerases and show that it performs as well as methods based on multiple sequence alignments.</p>
</sec>
<sec><title>Conclusion</title>
<p>We have presented and characterized a new alignment free method based on a mathematical kernel for scoring the similarity of protein sequences. We discuss possible improvements of this method, as well as an extension of its applications to other modeling methods that rely on sequence comparison.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Oldfield, Cj" uniqKey="Oldfield C">CJ Oldfield</name>
</author>
<author><name sortKey="Dunker, Ak" uniqKey="Dunker A">AK Dunker</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dill, Ka" uniqKey="Dill K">KA Dill</name>
</author>
<author><name sortKey="Ozkan, Sb" uniqKey="Ozkan S">SB Ozkan</name>
</author>
<author><name sortKey="Weikl, Tr" uniqKey="Weikl T">TR Weikl</name>
</author>
<author><name sortKey="Chodera, Jd" uniqKey="Chodera J">JD Chodera</name>
</author>
<author><name sortKey="Voelz, Va" uniqKey="Voelz V">VA Voelz</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Das, R" uniqKey="Das R">R Das</name>
</author>
<author><name sortKey="Baker, D" uniqKey="Baker D">D Baker</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bairoch, A" uniqKey="Bairoch A">A Bairoch</name>
</author>
<author><name sortKey="Apweiler, R" uniqKey="Apweiler R">R Apweiler</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Berman, Hm" uniqKey="Berman H">HM Berman</name>
</author>
<author><name sortKey="Westbrook, J" uniqKey="Westbrook J">J Westbrook</name>
</author>
<author><name sortKey="Feng, Z" uniqKey="Feng Z">Z Feng</name>
</author>
<author><name sortKey="Gilliland, G" uniqKey="Gilliland G">G Gilliland</name>
</author>
<author><name sortKey="Bhat, Tn" uniqKey="Bhat T">TN Bhat</name>
</author>
<author><name sortKey="Weissig, H" uniqKey="Weissig H">H Weissig</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Waterman, Ms" uniqKey="Waterman M">MS Waterman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name>
</author>
<author><name sortKey="Eddy, Sr" uniqKey="Eddy S">SR Eddy</name>
</author>
<author><name sortKey="Krogh, A" uniqKey="Krogh A">A Krogh</name>
</author>
<author><name sortKey="Mitchison, G" uniqKey="Mitchison G">G Mitchison</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gusfield, D" uniqKey="Gusfield D">D Gusfield</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schwartz, Rm" uniqKey="Schwartz R">RM Schwartz</name>
</author>
<author><name sortKey="Dayhoff, Mo" uniqKey="Dayhoff M">MO Dayhoff</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Henikoff, S" uniqKey="Henikoff S">S Henikoff</name>
</author>
<author><name sortKey="Henikoff, Jg" uniqKey="Henikoff J">JG Henikoff</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ladunga, I" uniqKey="Ladunga I">I Ladunga</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Smith, Tf" uniqKey="Smith T">TF Smith</name>
</author>
<author><name sortKey="Waterman, Ms" uniqKey="Waterman M">MS Waterman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Needleman, Sb" uniqKey="Needleman S">SB Needleman</name>
</author>
<author><name sortKey="Wunsch, Cd" uniqKey="Wunsch C">CD Wunsch</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Storey, Jd" uniqKey="Storey J">JD Storey</name>
</author>
<author><name sortKey="Sigmund, D" uniqKey="Sigmund D">D Sigmund</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rost, B" uniqKey="Rost B">B Rost</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wallace, Im" uniqKey="Wallace I">IM Wallace</name>
</author>
<author><name sortKey="Blackshields, G" uniqKey="Blackshields G">G Blackshields</name>
</author>
<author><name sortKey="Higgins, Dg" uniqKey="Higgins D">DG Higgins</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Vinga, S" uniqKey="Vinga S">S Vinga</name>
</author>
<author><name sortKey="Almeida, J" uniqKey="Almeida J">J Almeida</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bonham Carter, O" uniqKey="Bonham Carter O">O Bonham-Carter</name>
</author>
<author><name sortKey="Steele, J" uniqKey="Steele J">J Steele</name>
</author>
<author><name sortKey="Bastola, D" uniqKey="Bastola D">D Bastola</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Vinga, S" uniqKey="Vinga S">S Vinga</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schwende, I" uniqKey="Schwende I">I Schwende</name>
</author>
<author><name sortKey="Pham, Td" uniqKey="Pham T">TD Pham</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ulitsky, I" uniqKey="Ulitsky I">I Ulitsky</name>
</author>
<author><name sortKey="Burstein, D" uniqKey="Burstein D">D Burstein</name>
</author>
<author><name sortKey="Tuller, T" uniqKey="Tuller T">T Tuller</name>
</author>
<author><name sortKey="Chor, B" uniqKey="Chor B">B Chor</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Didier, G" uniqKey="Didier G">G Didier</name>
</author>
<author><name sortKey="Corel, E" uniqKey="Corel E">E Corel</name>
</author>
<author><name sortKey="Laprevotte, I" uniqKey="Laprevotte I">I Laprevotte</name>
</author>
<author><name sortKey="Grossmann, A" uniqKey="Grossmann A">A Grossmann</name>
</author>
<author><name sortKey="Landes Devauchelle, C" uniqKey="Landes Devauchelle C">C Landes-Devauchelle</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Burkhardt, S" uniqKey="Burkhardt S">S Burkhardt</name>
</author>
<author><name sortKey="K Rkk Inen, J" uniqKey="K Rkk Inen J">J Kärkkäinen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Keich, U" uniqKey="Keich U">U Keich</name>
</author>
<author><name sortKey="Li, M" uniqKey="Li M">M Li</name>
</author>
<author><name sortKey="Ma, B" uniqKey="Ma B">B Ma</name>
</author>
<author><name sortKey="Tromp, J" uniqKey="Tromp J">J Tromp</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Leimeister, Ca" uniqKey="Leimeister C">CA Leimeister</name>
</author>
<author><name sortKey="Boden, M" uniqKey="Boden M">M Boden</name>
</author>
<author><name sortKey="Horwege, S" uniqKey="Horwege S">S Horwege</name>
</author>
<author><name sortKey="Lindner, S" uniqKey="Lindner S">S Lindner</name>
</author>
<author><name sortKey="Morgenstern, B" uniqKey="Morgenstern B">B Morgenstern</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lodhi, H" uniqKey="Lodhi H">H Lodhi</name>
</author>
<author><name sortKey="Saunders, C" uniqKey="Saunders C">C Saunders</name>
</author>
<author><name sortKey="Shawe Taylor, J" uniqKey="Shawe Taylor J">J Shawe-Taylor</name>
</author>
<author><name sortKey="Cristianini, N" uniqKey="Cristianini N">N Cristianini</name>
</author>
<author><name sortKey="Watkins, C" uniqKey="Watkins C">C Watkins</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Diekhans, Tjm" uniqKey="Diekhans T">TJM Diekhans</name>
</author>
<author><name sortKey="Haussler, D" uniqKey="Haussler D">D Haussler</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Liao, L" uniqKey="Liao L">L Liao</name>
</author>
<author><name sortKey="Noble, Ws" uniqKey="Noble W">WS Noble</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Leslie, Cs" uniqKey="Leslie C">CS Leslie</name>
</author>
<author><name sortKey="Eskin, E" uniqKey="Eskin E">E Eskin</name>
</author>
<author><name sortKey="Cohen, A" uniqKey="Cohen A">A Cohen</name>
</author>
<author><name sortKey="Weston, J" uniqKey="Weston J">J Weston</name>
</author>
<author><name sortKey="Noble, Ws" uniqKey="Noble W">WS Noble</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="R Tsch, G" uniqKey="R Tsch G">G Rätsch</name>
</author>
<author><name sortKey="Sonnenburg, S" uniqKey="Sonnenburg S">S Sonnenburg</name>
</author>
<author><name sortKey="Scholkopf, B" uniqKey="Scholkopf B">B Schölkopf</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ben Hur, A" uniqKey="Ben Hur A">A Ben-Hur</name>
</author>
<author><name sortKey="Ong, Cs" uniqKey="Ong C">CS Ong</name>
</author>
<author><name sortKey="Sonnenburg, S" uniqKey="Sonnenburg S">S Sonnenburg</name>
</author>
<author><name sortKey="Scholkopf, B" uniqKey="Scholkopf B">B Schölkopf</name>
</author>
<author><name sortKey="R Tsch, M" uniqKey="R Tsch M">M Rätsch</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Saigo, H" uniqKey="Saigo H">H Saigo</name>
</author>
<author><name sortKey="Vert, Jp" uniqKey="Vert J">JP Vert</name>
</author>
<author><name sortKey="Ueda, N" uniqKey="Ueda N">N Ueda</name>
</author>
<author><name sortKey="Akutsu, T" uniqKey="Akutsu T">T Akutsu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Shen, Wj" uniqKey="Shen W">WJ Shen</name>
</author>
<author><name sortKey="Wong, Hs" uniqKey="Wong H">HS Wong</name>
</author>
<author><name sortKey="Xiao, Qw" uniqKey="Xiao Q">QW Xiao</name>
</author>
<author><name sortKey="Guo, X" uniqKey="Guo X">X Guo</name>
</author>
<author><name sortKey="Smale, S" uniqKey="Smale S">S Smale</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sillitoe, I" uniqKey="Sillitoe I">I Sillitoe</name>
</author>
<author><name sortKey="Lewis, Te" uniqKey="Lewis T">TE Lewis</name>
</author>
<author><name sortKey="Cuff, Al" uniqKey="Cuff A">AL Cuff</name>
</author>
<author><name sortKey="Das, S" uniqKey="Das S">S Das</name>
</author>
<author><name sortKey="Ashford, P" uniqKey="Ashford P">P Ashford</name>
</author>
<author><name sortKey="Dawson, Nl" uniqKey="Dawson N">NL Dawson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Thorne, Jl" uniqKey="Thorne J">JL Thorne</name>
</author>
<author><name sortKey="Kishino, H" uniqKey="Kishino H">H Kishino</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chan, Cx" uniqKey="Chan C">CX Chan</name>
</author>
<author><name sortKey="Ragan, Ma" uniqKey="Ragan M">MA Ragan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chan, Cx" uniqKey="Chan C">CX Chan</name>
</author>
<author><name sortKey="Bernard, G" uniqKey="Bernard G">G Bernard</name>
</author>
<author><name sortKey="Poirion, O" uniqKey="Poirion O">O Poirion</name>
</author>
<author><name sortKey="Hogan, Jm" uniqKey="Hogan J">JM Hogan</name>
</author>
<author><name sortKey="Ragan, Ma" uniqKey="Ragan M">MA Ragan</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Henikoff, S" uniqKey="Henikoff S">S Henikoff</name>
</author>
<author><name sortKey="Henikoff, J" uniqKey="Henikoff J">J Henikoff</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pearson, W" uniqKey="Pearson W">W Pearson</name>
</author>
<author><name sortKey="Lipman, D" uniqKey="Lipman D">D Lipman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Le, Q" uniqKey="Le Q">Q Le</name>
</author>
<author><name sortKey="Pollastri, G" uniqKey="Pollastri G">G Pollastri</name>
</author>
<author><name sortKey="Koehl, P" uniqKey="Koehl P">P Koehl</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, J" uniqKey="Li J">J Li</name>
</author>
<author><name sortKey="Koehl, P" uniqKey="Koehl P">P Koehl</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gribskov, M" uniqKey="Gribskov M">M Gribskov</name>
</author>
<author><name sortKey="Robinson, Nl" uniqKey="Robinson N">NL Robinson</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Subbiah, S" uniqKey="Subbiah S">S Subbiah</name>
</author>
<author><name sortKey="Laurents, Dv" uniqKey="Laurents D">DV Laurents</name>
</author>
<author><name sortKey="Levitt, M" uniqKey="Levitt M">M Levitt</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kolodny, R" uniqKey="Kolodny R">R Kolodny</name>
</author>
<author><name sortKey="Koehl, P" uniqKey="Koehl P">P Koehl</name>
</author>
<author><name sortKey="Levitt, M" uniqKey="Levitt M">M Levitt</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Rieck, K" uniqKey="Rieck K">K Rieck</name>
</author>
<author><name sortKey="Wresnegger, C" uniqKey="Wresnegger C">C Wresnegger</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chou, Kc" uniqKey="Chou K">KC Chou</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Xiao, X" uniqKey="Xiao X">X Xiao</name>
</author>
<author><name sortKey="Lin, Wz" uniqKey="Lin W">WZ Lin</name>
</author>
<author><name sortKey="Chou, Kc" uniqKey="Chou K">KC Chou</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Felsenstein, J" uniqKey="Felsenstein J">J Felsenstein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Chatzou, M" uniqKey="Chatzou M">M Chatzou</name>
</author>
<author><name sortKey="Magis, C" uniqKey="Magis C">C Magis</name>
</author>
<author><name sortKey="Chang, Jm" uniqKey="Chang J">JM Chang</name>
</author>
<author><name sortKey="Kemena, C" uniqKey="Kemena C">C Kemena</name>
</author>
<author><name sortKey="Bussotti, G" uniqKey="Bussotti G">G Bussotti</name>
</author>
<author><name sortKey="Erb, I" uniqKey="Erb I">I Erb</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hohl, M" uniqKey="Hohl M">M Höhl</name>
</author>
<author><name sortKey="Ragan, Ma" uniqKey="Ragan M">MA Ragan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wong, Km" uniqKey="Wong K">KM Wong</name>
</author>
<author><name sortKey="Suchard, Ma" uniqKey="Suchard M">MA Suchard</name>
</author>
<author><name sortKey="Huelsenbeck, Jp" uniqKey="Huelsenbeck J">JP Huelsenbeck</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wu, Mt" uniqKey="Wu M">MT Wu</name>
</author>
<author><name sortKey="Chatterji, S" uniqKey="Chatterji S">S Chatterji</name>
</author>
<author><name sortKey="Eisen, Ja" uniqKey="Eisen J">JA Eisen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Haubold, B" uniqKey="Haubold B">B Haubold</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Sievers, F" uniqKey="Sievers F">F Sievers</name>
</author>
<author><name sortKey="Wilm, A" uniqKey="Wilm A">A Wilm</name>
</author>
<author><name sortKey="Dineen, D" uniqKey="Dineen D">D Dineen</name>
</author>
<author><name sortKey="Gibson, Tj" uniqKey="Gibson T">TJ Gibson</name>
</author>
<author><name sortKey="Karplus, K" uniqKey="Karplus K">K Karplus</name>
</author>
<author><name sortKey="Li, W" uniqKey="Li W">W Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Felsenstein, J" uniqKey="Felsenstein J">J Felsenstein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Jones, Dt" uniqKey="Jones D">DT Jones</name>
</author>
<author><name sortKey="Taylor, Wr" uniqKey="Taylor W">WR Taylor</name>
</author>
<author><name sortKey="Thornton, Jm" uniqKey="Thornton J">JM Thornton</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fitch, Wm" uniqKey="Fitch W">WM Fitch</name>
</author>
<author><name sortKey="Margoliash, E" uniqKey="Margoliash E">E Margoliash</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kuhner, Mk" uniqKey="Kuhner M">MK Kuhner</name>
</author>
<author><name sortKey="Felsentein, J" uniqKey="Felsentein J">J Felsentein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kann, M" uniqKey="Kann M">M Kann</name>
</author>
<author><name sortKey="Qian, B" uniqKey="Qian B">B Qian</name>
</author>
<author><name sortKey="Goldstein, Ra" uniqKey="Goldstein R">RA Goldstein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Saigo, H" uniqKey="Saigo H">H Saigo</name>
</author>
<author><name sortKey="Vert, Jp" uniqKey="Vert J">JP Vert</name>
</author>
<author><name sortKey="Akutsu, T" uniqKey="Akutsu T">T Akutsu</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Bioinformatics</journal-id>
<journal-id journal-id-type="iso-abbrev">BMC Bioinformatics</journal-id>
<journal-title-group><journal-title>BMC Bioinformatics</journal-title>
</journal-title-group>
<issn pub-type="epub">1471-2105</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
<publisher-loc>London</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">28245816</article-id>
<article-id pub-id-type="pmc">5331664</article-id>
<article-id pub-id-type="publisher-id">1560</article-id>
<article-id pub-id-type="doi">10.1186/s12859-017-1560-9</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Methodology Article</subject>
</subj-group>
</article-categories>
<title-group><article-title>String kernels for protein sequence comparisons: improved fold recognition</article-title>
</title-group>
<contrib-group><contrib contrib-type="author"><name><surname>Nojoomi</surname>
<given-names>Saghi</given-names>
</name>
<address><email>sjnojoomi@ucdavis.edu</email>
</address>
<xref ref-type="aff" rid="Aff1">1</xref>
</contrib>
<contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">http://orcid.org/0000-0002-0908-068X</contrib-id>
<name><surname>Koehl</surname>
<given-names>Patrice</given-names>
</name>
<address><email>pakoehl@ucdavis.edu</email>
</address>
<xref ref-type="aff" rid="Aff2">2</xref>
</contrib>
<aff id="Aff1"><label>1</label>
Biotechnology program, University of California, Davis, 1, Shields Avenue, Davis, CA, 95616 USA</aff>
<aff id="Aff2"><label>2</label>
Department of Computer Science and Genome Center, 1, Shields Avenue, Davis, CA, 95616 USA</aff>
</contrib-group>
<pub-date pub-type="epub"><day>28</day>
<month>2</month>
<year>2017</year>
</pub-date>
<pub-date pub-type="pmc-release"><day>28</day>
<month>2</month>
<year>2017</year>
</pub-date>
<pub-date pub-type="collection"><year>2017</year>
</pub-date>
<volume>18</volume>
<elocation-id>137</elocation-id>
<history><date date-type="received"><day>21</day>
<month>10</month>
<year>2016</year>
</date>
<date date-type="accepted"><day>23</day>
<month>2</month>
<year>2017</year>
</date>
</history>
<permissions><copyright-statement>© The Author(s) 2017</copyright-statement>
<license license-type="OpenAccess"><license-p><bold>Open Access</bold>
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/publicdomain/zero/1.0/">http://creativecommons.org/publicdomain/zero/1.0/</ext-link>
) applies to the data made available in this article, unless otherwise stated.</license-p>
</license>
</permissions>
<abstract id="Abs1"><sec><title>Background</title>
<p>The amino acid sequence of a protein is the blueprint from which its structure and ultimately function can be derived. Therefore, sequence comparison methods remain essential for the determination of similarity between proteins. Traditional approaches for comparing two protein sequences begin with strings of letters (amino acids) that represent the sequences, before generating textual alignments between these strings and providing scores for each alignment. When the similitude between the two protein sequences to be compared is low however, the quality of the corresponding sequence alignment is usually poor, leading to poor performance for the recognition of similarity.</p>
</sec>
<sec><title>Results</title>
<p>In this study, we develop an alignment free alternative to these methods that is based on the concept of string kernels. Starting from recently proposed kernels on the discrete space of protein sequences (Shen et al, <italic>Found. Comput. Math.</italic>
, 2013,14:951-984), we introduce our own version, SeqKernel. Its implementation depends on two parameters, a coefficient that tunes the substitution matrix and the maximum length of <italic>k-mers</italic>
that it includes. We provide an exhaustive analysis of the impacts of these two parameters on the performance of SeqKernel for fold recognition. We show that with the right choice of parameters, use of the SeqKernel similarity measure improves fold recognition compared to the use of traditional alignment-based methods. We illustrate the application of SeqKernel to inferring phylogeny on RNA polymerases and show that it performs as well as methods based on multiple sequence alignments.</p>
</sec>
<sec><title>Conclusion</title>
<p>We have presented and characterized a new alignment free method based on a mathematical kernel for scoring the similarity of protein sequences. We discuss possible improvements of this method, as well as an extension of its applications to other modeling methods that rely on sequence comparison.</p>
</sec>
</abstract>
<kwd-group xml:lang="en"><title>Keywords</title>
<kwd>Protein sequence</kwd>
<kwd>Kernel</kwd>
<kwd>Alignment free methods</kwd>
</kwd-group>
<funding-group><award-group><funding-source><institution>Ministry of Education - Singapore</institution>
</funding-source>
<award-id>MOE2012-T3-1-008</award-id>
</award-group>
</funding-group>
<custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name>
<meta-value>© The Author(s) 2017</meta-value>
</custom-meta>
</custom-meta-group>
</article-meta>
</front>
<body><sec id="Sec1"><title>Background</title>
<p>The overall principles behind the translation of a gene sequence into an active protein structure are theoretically well understood. The sequence of nucleotides that forms a gene is first translated into a sequence of amino acids, based on the genetic code. The corresponding linear chain of amino acids becomes active only after it folds into a three-dimensional shape, the so-called tertiary structure of the protein (though there is mounting evidence that there is a whole class of “unstructured” proteins that are biologically relevant [<xref ref-type="bibr" rid="CR1">1</xref>
]). However, while we can easily observe experimentally how the linear chain folds, we do not understand the principles underlying that transition. For instance, the rules that reveals the three-dimensional structure of a protein from its amino acid sequence have not yet been unraveled. Finding these rules is in fact one of the “holy grails” in molecular biology, namely the protein structure prediction problem [<xref ref-type="bibr" rid="CR2">2</xref>
, <xref ref-type="bibr" rid="CR3">3</xref>
]. Efforts to solve this problem currently emphasize protein sequence analysis, as a consequence of the wealth of sequence data that is available. We know the primary sequences of many proteins, with currently more that 65,000,000 sequences in the TrEMBL database [<xref ref-type="bibr" rid="CR4">4</xref>
], we know in some cases the corresponding three-dimensional structures of these proteins, with more than 110,000 in the Protein Data Bank [<xref ref-type="bibr" rid="CR5">5</xref>
], and we have information on their biological activities, with more 550,000 sequences that have been annotated in SwissProt [<xref ref-type="bibr" rid="CR6">6</xref>
] (all numbers correspond to August 2016). However, we are still far from understanding all the information encoded in these databases. In this paper, we address the problem of protein sequence comparison in the context of protein fold recognition, and show that a new string kernel drastically improves the latter compared to traditional methods based on sequence alignment.</p>
<p>Amino acids are usually described using a one-letter code, and protein sequences are correspondingly represented as strings of letters. This representation has proved very useful, especially in the context of sequence alignment [<xref ref-type="bibr" rid="CR7">7</xref>
, <xref ref-type="bibr" rid="CR8">8</xref>
] that is usually performed using string-matching algorithms [<xref ref-type="bibr" rid="CR9">9</xref>
]. Those methods represent the overwhelming majority of methods used for sequence comparisons in bioinformatics. When comparing two sequences, they proceed in two steps, first the generation of the alignment between the two sequences, then the derivation of a statistical score for that alignment. They rely on a weighting scheme to measure the cost of matching pairs of amino acids. Many such weights have been proposed, from substitution matrices derived from evolution models such as the PAM matrices [<xref ref-type="bibr" rid="CR10">10</xref>
] and the BLOSUM matrices [<xref ref-type="bibr" rid="CR11">11</xref>
], to matrices that capture physico-chemical properties of amino acids [<xref ref-type="bibr" rid="CR12">12</xref>
]. Using this score, an alignment is derived following a dynamic programming algorithm, either the local method of Smith and Waterman [<xref ref-type="bibr" rid="CR13">13</xref>
], or the global method of Needleman and Wunsch [<xref ref-type="bibr" rid="CR14">14</xref>
]. This alignment is then scored by summing the individual weights of the matching pairs of amino acids and adding penalties for the presence of gaps. It should be noted that this score is not a metric in sequence space. Statistical methods have been developed to assess the significance of such scores, both for gapped and non-gapped alignments (see for example [<xref ref-type="bibr" rid="CR15">15</xref>
]). Such statistical scores are widely used for the identification of homologous sequences or for fold recognition. It has been shown however that those scores are efficient for both tasks for sequences with high similarities, but often fail for dissimilar sequences (see for example [<xref ref-type="bibr" rid="CR16">16</xref>
]). Extensions to pair-wise alignment methods have been proposed to alleviate this problem, such as those based on multiple sequence alignments and profiles [<xref ref-type="bibr" rid="CR17">17</xref>
], and those based on Hidden Markov Models [<xref ref-type="bibr" rid="CR8">8</xref>
]. While those show improved sensitivity, they remain prone to the problems related to the construction and use of alignments.</p>
<p>To circumvent the shortcomings of the alignment-based methods described above, many “alignment-free” methods have been proposed over the past three decades (for review, see [<xref ref-type="bibr" rid="CR18">18</xref>
–<xref ref-type="bibr" rid="CR20">20</xref>
]). Most of these methods compute the frequencies of words of a fixed length, <italic>k</italic>
, also denoted as <italic>k-mers</italic>
or <italic>k-grams</italic>
, depending on the authors. Once the frequency distribution functions of such <italic>k-mers</italic>
have been computed for two sequences, the distance between those two sequences is assimilated to the distance between those distributions, using different definitions of distance [<xref ref-type="bibr" rid="CR19">19</xref>
, <xref ref-type="bibr" rid="CR21">21</xref>
]. Other methods identify word matches of different lengths [<xref ref-type="bibr" rid="CR22">22</xref>
, <xref ref-type="bibr" rid="CR23">23</xref>
]. One such method, the <italic>average common substring approach</italic>
, identifies for each position <italic>i</italic>
in one sequence the longest substring starting at <italic>i</italic>
that is also present in the other sequence. The average lengths of those substrings over all positions <italic>i</italic>
is a measure of similarity of the two sequences that can be converted into a distance [<xref ref-type="bibr" rid="CR22">22</xref>
]. All those methods are based on exact word matches. Exact matches however are bound to have limitations, due to strong correlations between amino acids at neighboring positions. A solution to the limitations of exact matches is the <italic>spaced seeds</italic>
method that defines patterns with “<italic>match</italic>
” and possible “<italic>don’t care</italic>
” positions, using the vocabulary introduced by the authors [<xref ref-type="bibr" rid="CR24">24</xref>
–<xref ref-type="bibr" rid="CR27">27</xref>
].</p>
<p>Another class of alignment-free methods for comparing protein sequences that are directly relevant to this work includes string kernel based methods, originally defined in the context of support vector machines (SVM) [<xref ref-type="bibr" rid="CR28">28</xref>
]. SVM are machine learning algorithms that are designed to learn a rule for discrimination from a set of samples with two (or more) labels. This rule can then be applied to predict the label of any new sample. A key element of any SVM implementation is the kernel function that is used to quantify the similarity between any pair of samples. The simplest kernel function is the dot product between vectors of features that represent the samples. The first applications of SVM with a kernel function that is used to compute the similarity between two protein sequences were based on an extension of the dot product concept. Jakkola <italic>et al</italic>
[<xref ref-type="bibr" rid="CR29">29</xref>
] used a generative Hidden Markov Model (HMM) on a set of proteins to generate a vector representation of each protein sequence (the so-called Fisher score vector). The kernel is then defined as a dot product between the corresponding Fisher vectors. Lodhi and colleagues introduced a string kernel that counts the number of occurrences of subsequences of a fixed length in the two strings that are compared [<xref ref-type="bibr" rid="CR28">28</xref>
]. The SVM-pairwise method [<xref ref-type="bibr" rid="CR30">30</xref>
] consists of describing each sequence with a vector of pairwise similarity scores for all domains in the training set (where the similarity score is the E-value of the Smith-Waterman pairwise sequence alignment), and defines the kernel to be the dot product between these vector representations. The spectrum kernel [<xref ref-type="bibr" rid="CR31">31</xref>
] and the mismatch kernel [<xref ref-type="bibr" rid="CR32">32</xref>
] measure the similarity between protein sequences by quantifying the number of similar short substrings (i.e. <italic>k-mers</italic>
of fixed lengths, typically between 4 and 6 amino acids) they share. These two kernels bear similarity with the word-based alignment-free methods described above. The weighted degree kernels extend those kernels by considering weighted sums of the individual kernels obtained with fixed length <italic>k-mers</italic>
[<xref ref-type="bibr" rid="CR33">33</xref>
<italic>,</italic>
<xref ref-type="bibr" rid="CR34">34</xref>
]. The local alignment kernel of Saigo <italic>et al</italic>
[<xref ref-type="bibr" rid="CR35">35</xref>
] was designed to mimic the score generated by a Smith and Waterman pairwise alignment method, with the proper mathematical foundations to guarantee that it is a true kernel. More recently, Smale and co-workers expanded the local alignment kernel by considering all possible alignments of <italic>k-mers</italic>
between the two sequences of interest, for all possible <italic>k</italic>
values, ignoring gaps when aligning the <italic>k-mers</italic>
[<xref ref-type="bibr" rid="CR36">36</xref>
]. All the kernels listed here (as well as others that we have most likely missed), have been tested in classification problems as part of a machine learning algorithm (usually SVM), with various levels of success.</p>
<p>This paper draws from the concept of string kernels listed above. It describes an alignment-free method for protein sequence comparison that is based on the string kernel introduced by Smale and collaborators [<xref ref-type="bibr" rid="CR36">36</xref>
]. In contrast with the previous studies on string kernels, we do not include at this stage our string kernel into any learning algorithms. Instead, we assess directly its ability to classify proteins into structural folds based on sequence information only. We note that the string kernel we consider (which we refer to as SeqKernel) depends on two parameters, in addition to the substitution matrix it uses to score matches of pairs of amino acids (see below). We provide an exhaustive analysis of the effects of these two parameters on the performance of the kernel for fold recognition. Such an analysis, which is necessary as a first step to improving string kernel methods, was only partially included in the presentations of the equivalent kernels defined by Saigo <italic>et al</italic>
[<xref ref-type="bibr" rid="CR35">35</xref>
], and by Smale and co-workers [<xref ref-type="bibr" rid="CR36">36</xref>
]. In the latter study for example, one parameter, <italic>β</italic>
(see below for details), was fixed to 0.11, without further explanation, while the second parameter, <italic>k</italic>
<sub><italic>max</italic>
</sub>
, the maximum length of the <italic>k-mers</italic>
considered, is set to a small number for computational considerations. Finding how those parameters influence the performance of the kernel is the main focus of this paper. To perform this analysis, we consider different datasets of proteins that belong to different structural folds, as defined by CATH [<xref ref-type="bibr" rid="CR37">37</xref>
]. These proteins were selected such that their sequences share little sequence similarities. We classified these proteins using the similarity measure provided by the string kernels. The classification is then compared with the corresponding results obtained using the scores of pairwise sequence alignments and the scores of structural alignments of those proteins. Ultimately, we have observed that sequence alone provides poor separation of the different folds. We show in contrast that with the right choice of parameters, use of the string kernel similarity measure significantly improves classification accuracy. In addition, we illustrate the use of SeqKernel to reconstruct a phylogenic tree of RNA polymerases, in line with the current development of alignment-free methods for phylogenomics that are designed to remove problems inherent to (multiple) sequence alignments (see for example [<xref ref-type="bibr" rid="CR38">38</xref>
<italic>–</italic>
<xref ref-type="bibr" rid="CR40">40</xref>
]).</p>
<p>The paper is organized as follows. In “<xref rid="Sec2" ref-type="sec">Methods</xref>
” section, we describe the string kernel, while in “<xref rid="Sec14" ref-type="sec">Results and Discussion</xref>
” section we describe the databases we have generated to assess the performance of our string kernel for fold recognition. In the Results section, we provide a comprehensive analysis of the parameters that defined the kernel and finally we conclude the paper with a discussion on future developments of the string kernel approach.</p>
</sec>
<sec id="Sec2"><title>Methods</title>
<sec id="Sec3"><title>A string kernel for alignment-free sequence comparison</title>
<p>The string kernel considered here is inspired by the convolution string kernels introduced by D. Haussler [<xref ref-type="bibr" rid="CR41">41</xref>
], adapted by Saigo <italic>et al</italic>
[<xref ref-type="bibr" rid="CR35">35</xref>
] as the local alignment kernels, and later by Smale and co-workers [<xref ref-type="bibr" rid="CR36">36</xref>
]. We provide here the key elements of its construction. Readers should refer to the original papers for a more detailed presentation, notably for the proofs of the mathematical properties that are relevant to kernels in general.</p>
<p><bold>Notations</bold>
Let <italic>X</italic>
be a finite set of size <italic>n</italic>
. A kernel K is a symmetric function from <italic>X</italic>
×<italic>X</italic>
to <inline-formula id="IEq1"><alternatives><tex-math id="M1">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathbb {R}$\end{document}</tex-math>
<mml:math id="M2"><mml:mi>ℝ</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq1.gif"></inline-graphic>
</alternatives>
</inline-formula>
such that the Gram matrix <italic>G</italic>
of size <italic>n</italic>
×<italic>n</italic>
defined by <italic>G</italic>
(<italic>i</italic>
,<italic>j</italic>
)=<italic>K</italic>
(<italic>x</italic>
<sub><italic>i</italic>
</sub>
,<italic>x</italic>
<sub><italic>j</italic>
</sub>
) is symmetric, positive, and definite. Let <inline-formula id="IEq2"><alternatives><tex-math id="M3">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}$\end{document}</tex-math>
<mml:math id="M4"><mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq2.gif"></inline-graphic>
</alternatives>
</inline-formula>
be the set of the standard twenty amino acids found in proteins. A protein sequence <italic>S</italic>
is a string of elements from <inline-formula id="IEq3"><alternatives><tex-math id="M5">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}$\end{document}</tex-math>
<mml:math id="M6"><mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq3.gif"></inline-graphic>
</alternatives>
</inline-formula>
. We note |<italic>S</italic>
| the length of <italic>S</italic>
.</p>
<p><bold>A kernel for amino acid pairs.</bold>
Let <italic>SA</italic>
be a function from <inline-formula id="IEq4"><alternatives><tex-math id="M7">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}\times \mathcal {A}$\end{document}</tex-math>
<mml:math id="M8"><mml:mi mathvariant="script">A</mml:mi>
<mml:mo>×</mml:mo>
<mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq4.gif"></inline-graphic>
</alternatives>
</inline-formula>
to <inline-formula id="IEq5"><alternatives><tex-math id="M9">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathbb {R}$\end{document}</tex-math>
<mml:math id="M10"><mml:mi>ℝ</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq5.gif"></inline-graphic>
</alternatives>
</inline-formula>
, such that <italic>S</italic>
<italic>A</italic>
(<italic>i</italic>
,<italic>j</italic>
) measures the similarity of the amino acids <italic>i</italic>
and <italic>j</italic>
, and let <italic>SM</italic>
be the Gram matrix associated to <italic>SA</italic>
. Examples of <italic>SM</italic>
include the matrices representing the raw data of any BLOSUM matrices [<xref ref-type="bibr" rid="CR42">42</xref>
], namely the raw counts of how often amino acid <italic>i</italic>
is substituted by amino acid <italic>j</italic>
in a set of selected protein sequence alignments that is then normalized by considering its row sums <italic>P</italic>
(<italic>i</italic>
):
<disp-formula id="Equ1"><label>1</label>
<alternatives><tex-math id="M11">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} P(i) = \sum_{j=1}^{20} SM(i,j) \\ SM2(i,j) = \frac{SM(i,j)}{P(i)p(j)} \end{array} $$ \end{document}</tex-math>
<mml:math id="M12"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:mi>P</mml:mi>
<mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:munderover><mml:mrow><mml:mo>∑</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>j</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mn>20</mml:mn>
</mml:mrow>
</mml:munderover>
<mml:mtext mathvariant="italic">SM</mml:mtext>
<mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>)</mml:mo>
</mml:mtd>
<mml:mtd class="eqnarray-2"></mml:mtd>
<mml:mtd class="eqnarray-3"></mml:mtd>
<mml:mtd><mml:mtext></mml:mtext>
</mml:mtd>
</mml:mtr>
<mml:mtr><mml:mtd class="eqnarray-1"><mml:mtext mathvariant="italic">SM</mml:mtext>
<mml:mn>2</mml:mn>
<mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:mfrac><mml:mrow><mml:mtext mathvariant="italic">SM</mml:mtext>
<mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>P</mml:mi>
<mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>)</mml:mo>
<mml:mi>p</mml:mi>
<mml:mo>(</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mfrac>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ1.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>We have checked that when <italic>SM</italic>
is a raw count BLOSUM matrix, then <italic>S</italic>
<italic>M</italic>
2 is symmetric, positive, and definite. Note that when <italic>SM</italic>
is such a raw count matrix, the corresponding BLOSUM matrix <italic>BL</italic>
is defined as <italic>B</italic>
<italic>L</italic>
(<italic>i</italic>
,<italic>j</italic>
)=<italic>r</italic>
<italic>o</italic>
<italic>u</italic>
<italic>n</italic>
<italic>d</italic>
(<italic>l</italic>
<italic>o</italic>
<italic>g</italic>
<sub>2</sub>
(<italic>S</italic>
<italic>M</italic>
2(<italic>i</italic>
,<italic>j</italic>
))), where <italic>round</italic>
is the function that rounds a real number to its nearest integer. Given a strictly positive real number <italic>β</italic>
, we define the function <inline-formula id="IEq6"><alternatives><tex-math id="M13">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{1}: \mathcal {A}\times \mathcal {A} \rightarrow \mathbb {R}$\end{document}</tex-math>
<mml:math id="M14"><mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>1</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>:</mml:mo>
<mml:mi mathvariant="script">A</mml:mi>
<mml:mo>×</mml:mo>
<mml:mi mathvariant="script">A</mml:mi>
<mml:mo>→</mml:mo>
<mml:mi>ℝ</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq6.gif"></inline-graphic>
</alternatives>
</inline-formula>
as:
<disp-formula id="Equ2"><label>2</label>
<alternatives><tex-math id="M15">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} K_{1}(i,j) = SM2(i,j)^{\beta} \end{array} $$ \end{document}</tex-math>
<mml:math id="M16"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>1</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:mtext mathvariant="italic">SM</mml:mtext>
<mml:mn>2</mml:mn>
<mml:msup><mml:mrow><mml:mo>(</mml:mo>
<mml:mi>i</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>j</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>β</mml:mi>
</mml:mrow>
</mml:msup>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ2.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p><italic>K</italic>
<sub>1</sub>
is a kernel function on <inline-formula id="IEq7"><alternatives><tex-math id="M17">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}\times \mathcal {A}$\end{document}</tex-math>
<mml:math id="M18"><mml:mi mathvariant="script">A</mml:mi>
<mml:mo>×</mml:mo>
<mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq7.gif"></inline-graphic>
</alternatives>
</inline-formula>
, as long as <italic>S</italic>
<italic>M</italic>
2 is symmetric, positive, definite, and <italic>β</italic>
is strictly positive. The same definition was used in [<xref ref-type="bibr" rid="CR36">36</xref>
].</p>
<p><bold>A kernel for comparing two strings of the same length.</bold>
Let <italic>k</italic>
be a strictly positive integer and let <inline-formula id="IEq8"><alternatives><tex-math id="M19">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}^{k}$\end{document}</tex-math>
<mml:math id="M20"><mml:msup><mml:mrow><mml:mi mathvariant="script">A</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq8.gif"></inline-graphic>
</alternatives>
</inline-formula>
be the <italic>k</italic>
-th Cartesian power of <inline-formula id="IEq9"><alternatives><tex-math id="M21">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}$\end{document}</tex-math>
<mml:math id="M22"><mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq9.gif"></inline-graphic>
</alternatives>
</inline-formula>
. An element of <inline-formula id="IEq10"><alternatives><tex-math id="M23">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}^{k}$\end{document}</tex-math>
<mml:math id="M24"><mml:msup><mml:mrow><mml:mi mathvariant="script">A</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq10.gif"></inline-graphic>
</alternatives>
</inline-formula>
is a string of <italic>k</italic>
letters taken from <inline-formula id="IEq11"><alternatives><tex-math id="M25">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}$\end{document}</tex-math>
<mml:math id="M26"><mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq11.gif"></inline-graphic>
</alternatives>
</inline-formula>
, it is usually referred to as a <italic>k-mer</italic>
, or a <italic>k-gram</italic>
. Let <italic>u</italic>
<sup><italic>k</italic>
</sup>
=(<italic>u</italic>
<sub>1</sub>
,…,<italic>u</italic>
<sub><italic>k</italic>
</sub>
) and <italic>υ</italic>
<sup><italic>k</italic>
</sup>
=(<italic>υ</italic>
<sub>1</sub>
,…,<italic>υ</italic>
<sub><italic>k</italic>
</sub>
) be two <italic>k-mers</italic>
in <inline-formula id="IEq12"><alternatives><tex-math id="M27">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}^{k}$\end{document}</tex-math>
<mml:math id="M28"><mml:msup><mml:mrow><mml:mi mathvariant="script">A</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq12.gif"></inline-graphic>
</alternatives>
</inline-formula>
. The function <inline-formula id="IEq13"><alternatives><tex-math id="M29">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{2}^{k}$\end{document}</tex-math>
<mml:math id="M30"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq13.gif"></inline-graphic>
</alternatives>
</inline-formula>
defined by:
<disp-formula id="Equ3"><label>3</label>
<alternatives><tex-math id="M31">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} K_{2}^{k}(u^{k},\upsilon{k}) = \prod_{i=1}^{k} K_{1}(u_{i},\upsilon_{i}) \end{array} $$ \end{document}</tex-math>
<mml:math id="M32"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:mo>(</mml:mo>
<mml:msup><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:mi>υk</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:munderover><mml:mrow><mml:mo>∏</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:munderover>
<mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>1</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:msub><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>,</mml:mo>
<mml:msub><mml:mrow><mml:mi>υ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>)</mml:mo>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ3.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>is a kernel on <inline-formula id="IEq14"><alternatives><tex-math id="M33">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}^{k}$\end{document}</tex-math>
<mml:math id="M34"><mml:msup><mml:mrow><mml:mi mathvariant="script">A</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq14.gif"></inline-graphic>
</alternatives>
</inline-formula>
, the set of all <italic>k-mers</italic>
. We note that <inline-formula id="IEq15"><alternatives><tex-math id="M35">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{2}^{k}$\end{document}</tex-math>
<mml:math id="M36"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq15.gif"></inline-graphic>
</alternatives>
</inline-formula>
is a convolution kernel [<xref ref-type="bibr" rid="CR41">41</xref>
].</p>
<p><bold>A kernel for computing protein sequence similarity.</bold>
Let <italic>S</italic>
=(<italic>s</italic>
<sub>1</sub>
,…,<italic>s</italic>
<sub><italic>n</italic>
</sub>
) and <italic>T</italic>
=(<italic>t</italic>
<sub>1</sub>
,…,<italic>t</italic>
<sub><italic>m</italic>
</sub>
) be two protein sequences; both are strings, with <inline-formula id="IEq16"><alternatives><tex-math id="M37">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$S \in \mathcal {A}^{n}$\end{document}</tex-math>
<mml:math id="M38"><mml:mi>S</mml:mi>
<mml:mo>∈</mml:mo>
<mml:msup><mml:mrow><mml:mi mathvariant="script">A</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq16.gif"></inline-graphic>
</alternatives>
</inline-formula>
and <inline-formula id="IEq17"><alternatives><tex-math id="M39">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$T \in \mathcal {A}^{m}$\end{document}</tex-math>
<mml:math id="M40"><mml:mi>T</mml:mi>
<mml:mo>∈</mml:mo>
<mml:msup><mml:mrow><mml:mi mathvariant="script">A</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>m</mml:mi>
</mml:mrow>
</mml:msup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq17.gif"></inline-graphic>
</alternatives>
</inline-formula>
. Let <italic>u</italic>
<sup><italic>k</italic>
</sup>
and <italic>υ</italic>
<sup><italic>k</italic>
</sup>
be substrings of length <italic>k</italic>
(i.e. <italic>k-mers</italic>
) of <italic>S</italic>
and <italic>T</italic>
respectively. <italic>u</italic>
<sup><italic>k</italic>
</sup>
and <italic>υ</italic>
<sup><italic>k</italic>
</sup>
are considered contiguous, i.e. we do not allow gaps. There are therefore <italic>n</italic>
−<italic>k</italic>
+1 and <italic>m</italic>
−<italic>k</italic>
+1 such substrings in <italic>S</italic>
and <italic>T</italic>
, respectively. We define
<disp-formula id="Equ4"><label>4</label>
<alternatives><tex-math id="M41">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} K_{3}^{k}(S,T) = \sum_{u^{k} \in S} \sum_{\upsilon^{k} \in T} K_{2}^{k}(u^{k},\upsilon^{k}) \end{array} $$ \end{document}</tex-math>
<mml:math id="M42"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:munder><mml:mrow><mml:mo>∑</mml:mo>
</mml:mrow>
<mml:mrow><mml:msup><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>∈</mml:mo>
<mml:mi>S</mml:mi>
</mml:mrow>
</mml:munder>
<mml:munder><mml:mrow><mml:mo>∑</mml:mo>
</mml:mrow>
<mml:mrow><mml:msup><mml:mrow><mml:mi>υ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>∈</mml:mo>
<mml:mi>T</mml:mi>
</mml:mrow>
</mml:munder>
<mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:mo>(</mml:mo>
<mml:msup><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:msup><mml:mrow><mml:mi>υ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>)</mml:mo>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ4.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>and
<disp-formula id="Equ5"><label>5</label>
<alternatives><tex-math id="M43">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} K_{3}(S,T) = \sum_{k=1}^{p} K_{3}^{k}(S,T). \end{array} $$ \end{document}</tex-math>
<mml:math id="M44"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:munderover><mml:mrow><mml:mo>∑</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>p</mml:mi>
</mml:mrow>
</mml:munderover>
<mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mi>.</mml:mi>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ5.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>where the summation extends to <italic>p</italic>
= min(<italic>n</italic>
,<italic>m</italic>
),with <italic>n</italic>
and <italic>m</italic>
the lengths of the two sequences that are compared. Finally, we define the correlation kernel <inline-formula id="IEq18"><alternatives><tex-math id="M45">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}$\end{document}</tex-math>
<mml:math id="M46"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq18.gif"></inline-graphic>
</alternatives>
</inline-formula>
as:
<disp-formula id="Equ6"><label>6</label>
<alternatives><tex-math id="M47">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} \hat{K}_{3}(S,T) = \frac{K_{3}(S,T)}{\sqrt{K_{3}(S,S)K_{3}(T,T)}} \end{array} $$ \end{document}</tex-math>
<mml:math id="M48"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:mfrac><mml:mrow><mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mrow><mml:msqrt><mml:mrow><mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>)</mml:mo>
<mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:msqrt>
</mml:mrow>
</mml:mfrac>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ6.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>Following [<xref ref-type="bibr" rid="CR41">41</xref>
] and [<xref ref-type="bibr" rid="CR36">36</xref>
], we make the following remarks:
<list list-type="simple"><list-item><label>i)</label>
<p>The input kernel matrix <italic>SM</italic>
is not a traditional substitution matrix, as it does not involve applying the logarithm function on the probability measures. While the latter is needed to make scores additive, a necessary condition for the use of dynamic programming algorithms in generating pairwise sequence alignment, it is not needed for the string kernel we use here. Note that this differs from the local alignment kernel, which is designed to mimic pairwise alignment.</p>
</list-item>
<list-item><label>ii)</label>
<p>The kernel <italic>K</italic>
<sub>3</sub>
is computed as an unweighted sum of the individual kernels <inline-formula id="IEq19"><alternatives><tex-math id="M49">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{3}^{k}$\end{document}</tex-math>
<mml:math id="M50"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq19.gif"></inline-graphic>
</alternatives>
</inline-formula>
that are computed with a fixed <italic>k</italic>
value. We could have considered a weighted sum instead, similar in spirit to the weighted degree kernels [<xref ref-type="bibr" rid="CR34">34</xref>
]. We leave this option for future work.</p>
</list-item>
<list-item><label>iii)</label>
<p>The summation in Eq. <xref rid="Equ5" ref-type="">5</xref>
extends to the length of the smallest sequence. This summation can be truncated however to only include <italic>k-mers</italic>
up to a fixed length set to be <italic>k</italic>
<sub><italic>max</italic>
</sub>
. This will be discussed in details.</p>
</list-item>
<list-item><label>iv)</label>
<p><inline-formula id="IEq20"><alternatives><tex-math id="M51">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}$\end{document}</tex-math>
<mml:math id="M52"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq20.gif"></inline-graphic>
</alternatives>
</inline-formula>
is a kernel as long as <italic>S</italic>
<italic>M</italic>
2 and <italic>β</italic>
(which define <italic>K</italic>
<sub>1</sub>
) are definite positive, and strictly positive, respectively. Note that for any kernel <italic>K</italic>
<sub>1</sub>
defined on <inline-formula id="IEq21"><alternatives><tex-math id="M53">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {A}\times \mathcal {A}$\end{document}</tex-math>
<mml:math id="M54"><mml:mi mathvariant="script">A</mml:mi>
<mml:mo>×</mml:mo>
<mml:mi mathvariant="script">A</mml:mi>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq21.gif"></inline-graphic>
</alternatives>
</inline-formula>
, we can define a correlation string kernel <inline-formula id="IEq22"><alternatives><tex-math id="M55">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}$\end{document}</tex-math>
<mml:math id="M56"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq22.gif"></inline-graphic>
</alternatives>
</inline-formula>
.</p>
</list-item>
<list-item><label>v)</label>
<p>As defined, <inline-formula id="IEq23"><alternatives><tex-math id="M57">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}$\end{document}</tex-math>
<mml:math id="M58"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq23.gif"></inline-graphic>
</alternatives>
</inline-formula>
does not consider gap penalties, or even gaps. We consider this as an advantage, as it does reduce the number of parameters that defines <inline-formula id="IEq24"><alternatives><tex-math id="M59">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}$\end{document}</tex-math>
<mml:math id="M60"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq24.gif"></inline-graphic>
</alternatives>
</inline-formula>
.</p>
</list-item>
<list-item><label>vi)</label>
<p>The string kernel <inline-formula id="IEq25"><alternatives><tex-math id="M61">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}$\end{document}</tex-math>
<mml:math id="M62"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq25.gif"></inline-graphic>
</alternatives>
</inline-formula>
is a similarity measure in the space of sequences. Notice that for all sequences <italic>S</italic>
, <inline-formula id="IEq26"><alternatives><tex-math id="M63">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\hat {K}_{3}(S) = 1$\end{document}</tex-math>
<mml:math id="M64"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq26.gif"></inline-graphic>
</alternatives>
</inline-formula>
. This similarity measure can be transformed into a distance measure, using <inline-formula id="IEq27"><alternatives><tex-math id="M65">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$D(S,T) = \sqrt {\hat {K}_{3}(S,S)+\hat {K}_{3}(T,T)-2\hat {K}_{3}(S,T)}=\sqrt {2-2\hat {K}_{3}(S,T)}$\end{document}</tex-math>
<mml:math id="M66"><mml:mi>D</mml:mi>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:msqrt><mml:mrow><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>+</mml:mo>
<mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>−</mml:mo>
<mml:mn>2</mml:mn>
<mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:msqrt>
<mml:mo>=</mml:mo>
<mml:msqrt><mml:mrow><mml:mn>2</mml:mn>
<mml:mo>−</mml:mo>
<mml:mn>2</mml:mn>
<mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mo>^</mml:mo>
</mml:mover>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:msqrt>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq27.gif"></inline-graphic>
</alternatives>
</inline-formula>
. <italic>D</italic>
(<italic>S</italic>
,<italic>T</italic>
) takes values between 0 and <inline-formula id="IEq28"><alternatives><tex-math id="M67">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\sqrt {2}$\end{document}</tex-math>
<mml:math id="M68"><mml:msqrt><mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
</mml:msqrt>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq28.gif"></inline-graphic>
</alternatives>
</inline-formula>
.</p>
</list-item>
</list>
</p>
</sec>
<sec id="Sec8"><title>Implementing the string kernel</title>
<p>Equation <xref rid="Equ5" ref-type="">5</xref>
above leads to a simple, naive algorithm for computing the <italic>K</italic>
<sub>3</sub>
kernel for two sequences <italic>S</italic>
and <italic>T</italic>
: for any length <italic>k</italic>
, generate all <italic>n</italic>
−<italic>k</italic>
+1 and <italic>m</italic>
−<italic>k</italic>
+1<italic>k-mers</italic>
in <italic>S</italic>
and <italic>T</italic>
, and perform the (<italic>n</italic>
−<italic>k</italic>
+1)(<italic>m</italic>
−<italic>k</italic>
+1) corresponding <inline-formula id="IEq29"><alternatives><tex-math id="M69">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{2}^{k}$\end{document}</tex-math>
<mml:math id="M70"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq29.gif"></inline-graphic>
</alternatives>
</inline-formula>
kernel evaluations using Eq. <xref rid="Equ3" ref-type="">3</xref>
. Such an implementation however would come at a high computing cost, namely <inline-formula id="IEq30"><alternatives><tex-math id="M71">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$O({nmk}_{max}^{2})$\end{document}</tex-math>
<mml:math id="M72"><mml:mi>O</mml:mi>
<mml:mo>(</mml:mo>
<mml:msubsup><mml:mrow><mml:mtext mathvariant="italic">nmk</mml:mtext>
</mml:mrow>
<mml:mrow><mml:mtext mathvariant="italic">max</mml:mtext>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
</mml:msubsup>
<mml:mo>)</mml:mo>
</mml:math>
<inline-graphic xlink:href="12859_2017_1560_Article_IEq30.gif"></inline-graphic>
</alternatives>
</inline-formula>
, where <italic>n</italic>
and <italic>m</italic>
are the lengths of <italic>S</italic>
and <italic>T</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
is the longest <italic>k-mer</italic>
considered. We notice however that for any <italic>k-mers</italic>
<italic>u</italic>
<sup><italic>k</italic>
</sup>
and <italic>υ</italic>
<sup><italic>k</italic>
</sup>
, we have:
<disp-formula id="Equ7"><label>7</label>
<alternatives><tex-math id="M73">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} K_{2}^{k}(u^{k},\upsilon^{k}) = K_{2}^{k-1}(u^{k-1}, \upsilon^{k-1}) K_{1}(u^{k},\upsilon^{k}) \end{array} $$ \end{document}</tex-math>
<mml:math id="M74"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msubsup>
<mml:mo>(</mml:mo>
<mml:msup><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:msup><mml:mrow><mml:mi>υ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:msubsup><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
<mml:mo>−</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
</mml:msubsup>
<mml:mo>(</mml:mo>
<mml:msup><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
<mml:mo>−</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:msup><mml:mrow><mml:mi>υ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
<mml:mo>−</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
</mml:msup>
<mml:mo>)</mml:mo>
<mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>1</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:msup><mml:mrow><mml:mi>u</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>,</mml:mo>
<mml:msup><mml:mrow><mml:mi>υ</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
</mml:msup>
<mml:mo>)</mml:mo>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ7.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>where <italic>u</italic>
<sup><italic>k</italic>
−1</sup>
is the string of length <italic>k</italic>
−1 formed from the <italic>k</italic>
−1 first components of <italic>u</italic>
<sup><italic>k</italic>
</sup>
(with a similar definition for <italic>υ</italic>
<sup><italic>k</italic>
−1</sup>
). This simple recursion formula leads to a more efficient algorithm for computing the string kernel <italic>K</italic>
<sub>3</sub>
of order <italic>O</italic>
(<italic>n</italic>
<italic>m</italic>
<italic>k</italic>
<sub><italic>max</italic>
</sub>
). We note that this complexity remains large for protein sequence comparison.</p>
</sec>
<sec id="Sec9"><title>Datasets of protein sequences</title>
<p>Our first dataset includes 10,619 domains from the CATH [<xref ref-type="bibr" rid="CR37">37</xref>
] v4.0 domains, each with a CATH classification. As we focus on protein structure fold prediction, we consider the first three layers of the CATH classification, namely, Class (C), Architecture (A), and Topology (T). A set of structures with the same C, A, and T defines a fold. By using a set of structures with significant sequence diversity, we ensure that the data is duplicate-free. Such a filter when selecting the sequences also assures that the problem of detecting structural similarity is non-trivial. The 10619 structures were selected as follows: (i) Randomize the list of 235,858 CATH v4.0 domains; (ii) Start with the first domain on the randomized list, and remove from the list all domains that share significant sequence similarity with it (FASTA [<xref ref-type="bibr" rid="CR43">43</xref>
] SSEARCH E-value <10<sup>−4</sup>
, with the alignments computed with the BLOSUM62 substitution matrix [<xref ref-type="bibr" rid="CR42">42</xref>
], and gap penalties of -11 (opening) and -1 (extension)). (iii) Repeat step (ii) with all domains in the list that have not yet been removed, until there are no domains left for selection. The set of 10619 domains resulting from this procedure is referred to as CATH40e4.</p>
<p>There are 1363 folds in CATH40e4, many of which only include a single representative (734). To improve statistical analysis and remove possible biases from those folds with a low number of representative, we selected five of the most populated folds in CATH40e4 as a more specific test set, including at least one fold from each CATH class: CATH fold 1.10.10, a fully <italic>α</italic>
fold (arc repressor, 381 members), CATH fold 2.60.40, a fully <italic>β</italic>
fold (immunoglobulin-like, 555 members), and three alternating <italic>α</italic>
/<italic>β</italic>
folds: 3.20.20, (TIM-like, 251 members), 3.30.70, (two layer sandwich, 368 members) and 3.40.50 (Rossmann fold, 1278 members). The same five folds were previously used in other studies [<xref ref-type="bibr" rid="CR44">44</xref>
<italic>,</italic>
<xref ref-type="bibr" rid="CR45">45</xref>
], but with different members as based on a different version of CATH. Overall, these five folds consist of a total of 2833 proteins (set CATH2833). Table <xref rid="Tab1" ref-type="table">1</xref>
provides general information about the distributions of proteins in those five folds, while Fig. <xref rid="Fig1" ref-type="fig">1</xref>
illustrates the geometries of those folds, using the structure representatives defined by CATH.
<fig id="Fig1"><label>Fig. 1</label>
<caption><p>Representatives of the five fold classes in our test set CATH2833. The arc repressor mutant, subunit A fold (CATH 1.10.10) is a common orthogonal helix bundle, found, for example, in the Zb domain from the RNA editing human enzyme ADAR1 (CATH code 1xmkA00). The immunoglobulin-like fold is a <italic>β</italic>
sandwich, found in many immunoglobulin-like proteins, such as the human MCG protein (CATH code 4unuA00). The TIM barrel is a very common <italic>α</italic>
/<italic>β</italic>
fold, shown in an isomerase of the parasite <italic>Leishmania mexicana</italic>
(CATH code 2vxnA00). The <italic>α</italic>
−<italic>β</italic>
plait fold is a two-layer sandwich, shown here in a human nucleoprotein, HNRNP (CATH code 1l3kA01). The Rossmann fold is a very common three-layer sandwich fold in the mixed <italic>α</italic>
−<italic>β</italic>
class, found, for example, in the D-amino acic oxydase from <italic>Rhodotorula toruloides</italic>
(CATH code 1c0pA01). All images were generated using Pymol <ext-link ext-link-type="uri" xlink:href="http://www.pymol.org">http://www.pymol.org</ext-link>
</p>
</caption>
<graphic xlink:href="12859_2017_1560_Fig1_HTML" id="MO1"></graphic>
</fig>
<table-wrap id="Tab1"><label>Table 1</label>
<caption><p>Statistics of the sequences included in the two datasets</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left"></th>
<th align="left"></th>
<th align="left" colspan="2">Dataset</th>
<th align="left"></th>
</tr>
<tr><th align="left"></th>
<th align="left" colspan="2">CATH2833</th>
<th align="left" colspan="2">CATH793</th>
</tr>
<tr><th align="left">CATH fold ID</th>
<th align="left">N<sup>a</sup>
</th>
<th align="left">L (SD)<sup>b</sup>
</th>
<th align="left">N</th>
<th align="left">L (SD)</th>
</tr>
</thead>
<tbody><tr><td align="left">1.10.10</td>
<td align="left">381</td>
<td align="left">79 (26)</td>
<td align="left">36</td>
<td align="left">135 (10)</td>
</tr>
<tr><td align="left">2.60.40</td>
<td align="left">555</td>
<td align="left">110 (29)</td>
<td align="left">130</td>
<td align="left">140 (16)</td>
</tr>
<tr><td align="left">3.20.20</td>
<td align="left">251</td>
<td align="left">294 (69)</td>
<td align="left">2</td>
<td align="left">157 (14)</td>
</tr>
<tr><td align="left">3.30.70</td>
<td align="left">368</td>
<td align="left">182 (59)</td>
<td align="left">52</td>
<td align="left">141 (18)</td>
</tr>
<tr><td align="left">3.40.50</td>
<td align="left">1278</td>
<td align="left">153 (77)</td>
<td align="left">573</td>
<td align="left">151 (17)</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p><sup>a</sup>
Number of proteins in the fold</p>
<p><sup>b</sup>
Mean (standard deviation) of the lengths of the proteins in the fold</p>
</table-wrap-foot>
</table-wrap>
</p>
<p>As seen in Table <xref rid="Tab1" ref-type="table">1</xref>
, the proteins in the five folds included in CATH2833 vary significantly in length. To assess the importance of length differences when computing the string kernel between two sequences, we generated a subset of CATH2833, CATH793, that contains all proteins whose lengths are between 120 and 180 amino acids. General information about those proteins is available in Table <xref rid="Tab1" ref-type="table">1</xref>
.</p>
<p>Finally, we extracted a second dataset from CATH40e4 that contains all folds with at least 40 representatives, excluding the five folds included in CATH2833. There are 40 of those folds, covering all three classes of proteins, and 13 architectures. This dataset contains a total of 3744 proteins and is referred to as CATH3744.</p>
</sec>
<sec id="Sec10"><title>ROC analysis of protein fold recognition</title>
<p>We quantify the effectiveness of a distance measure in identifying correctly if two sequences correspond to proteins that belong to the same CATH group using the receiver operating characteristic (ROC) analysis [<xref ref-type="bibr" rid="CR46">46</xref>
]. In the following, a “group” may be the class of the sequence (i.e. <italic>α</italic>
, <italic>β</italic>
, or <italic>α</italic>
/<italic>β</italic>
), the architecture of the corresponding protein structure, or the topology of the protein structure, as defined by CATH. A pair of protein sequences is defined as similar, or “positive”, if the sequences are members of the same group, and “negative” otherwise. All pairs of protein sequences in a dataset are then compared using a similarity measure. For varying thresholds of the measure considered, all pairs that fall below the threshold are assumed to be positive, and all above it are considered negative. The pairs that agree with the assumed standard are then called true positives (TP), while those that do not are deemed false positives (FP). A ROC analysis is set to measure the rate of TP as a function of the rate of FP. The “quality” of the similarity measure, namely its ability to separate positive pairs from negative pairs, is then scored using the Area Under the corresponding Curve, namely the AUC. An AUC score of 1 would indicate that all TP are detected first: this is consistent with an ideal measure. An AUC score of 0.5 indicates that TP and FP follow the first diagonal: they therefore appear at the same rate, indicating that the measure is not discerning.</p>
<p>When the number of groups considered is larger than two, we have performed two types of ROC analyses. In the first approach, we label a pair of proteins that belong to a given group as positive, independent of the group considered. In this case, an average behavior over all possible groups is derived. In the second approach, only pairs of proteins that belong to a specific group are called positive. This provides a group specific ROC analysis.</p>
</sec>
<sec id="Sec11"><title>Fold classification experiments</title>
<p>The ROC analysis described above ranks the distance measures of pairs of protein sequences and checks if this ranking is consistent with an existing classification; it is not designed to achieve the classification itself. We have expanded the ROC analysis to the actual issue of fold recognition by carrying out a second set of experiments. Each experiment involves a data set of protein sequences, <italic>D</italic>
, a level of classification with groups, <italic>G</italic>
, and a distance measure, <italic>d</italic>
. We start by dividing randomly the sets of sequences in <italic>D</italic>
into two subsets of approximately equal size. The first subset defines a training set, while the second subset corresponds to the test set. A test sequence is assigned a class by mapping it to the group of its nearest neighbor in the training set. Here the nearest neighbor is found by computing first the mean normalized distance between the test sequence and all sequences in the training set that belongs to a given group, for all groups in the training set, and then taking the smallest of those mean distances. The results are gathered in a confusion matrix, <italic>C</italic>
, whose element <italic>C</italic>
(<italic>i</italic>
,<italic>j</italic>
) corresponds to the number of test sequences from group <italic>i</italic>
that have been classified as belonging to group <italic>j</italic>
. The efficiency of the classifier <italic>d</italic>
is then defined to be the quotient of the trace of the confusion matrix over the sum of all its elements. This quotient corresponds to the percentage of correctly classified sequences.</p>
</sec>
<sec id="Sec12"><title>Protein structure comparison</title>
<p>We have used STRUCTAL [<xref ref-type="bibr" rid="CR47">47</xref>
] to perform geometric alignments of two curves representing two protein structures. STRUCTAL starts with an initial alignment (a correspondence between residues of the two structures), and computes the rigid-body transformation that leads to the “best” geometric superimposition of the corresponding residues. It then identifies an optimal alignment for this superposition, using dynamic programming. The new alignment defines a new correspondence, which is used to superimpose the structures again. This procedure is then iterated until it converges to a local optimum that depends on the initial alignment. To alleviate biases due to that dependence, STRUCTAL repeats the iterative search using several different initial correspondences.</p>
<p>The traditional measure of similarity between two protein structures after optimal alignment is the root mean square displacement of atomic positions, also called cRMS for coordinate root mean square displacement, computed as:
<disp-formula id="Equ8"><label>8</label>
<alternatives><tex-math id="M75">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} cRMS = \sqrt{\frac{\sum_{i=1}^{N} \text{dist}(a_{i},b_{i})}{N}} \end{array} $$ \end{document}</tex-math>
<mml:math id="M76"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:mtext mathvariant="italic">cRMS</mml:mtext>
<mml:mo>=</mml:mo>
<mml:msqrt><mml:mrow><mml:mfrac><mml:mrow><mml:munderover><mml:mrow><mml:mo>∑</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:mi>N</mml:mi>
</mml:mrow>
</mml:munderover>
<mml:mtext>dist</mml:mtext>
<mml:mo>(</mml:mo>
<mml:msub><mml:mrow><mml:mi>a</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>,</mml:mo>
<mml:msub><mml:mrow><mml:mi>b</mml:mi>
</mml:mrow>
<mml:mrow><mml:mi>i</mml:mi>
</mml:mrow>
</mml:msub>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>N</mml:mi>
</mml:mrow>
</mml:mfrac>
</mml:mrow>
</mml:msqrt>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ8.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>where N is the number of positions in the correspondence, and <italic>a</italic>
<sub><italic>i</italic>
</sub>
and <italic>b</italic>
<sub><italic>i</italic>
</sub>
are the Cartesian positions of two residues <italic>a</italic>
and <italic>b</italic>
from the two structures. The cRMS however is not a good measure of structural similarity [<xref ref-type="bibr" rid="CR48">48</xref>
]. Intuitively, a “good” measure of geometric, or structural similarity should favor alignments with many residues that are matched, low cRMS deviations, and few gaps. Unfortunately, these properties are not unrelated. For example, a lower cRMS deviation can always be achieved by selecting a smaller number of matches. In fact, given the fixed inter-CA distance there is the extreme case of alignments that only include two residues that have cRMS deviations of exactly zero. Also, the addition of gaps may lengthen the alignment without increasing the cRMS value. Different similarity measures have been proposed that attempt to balance these values in different ways. In this work, we have implemented the Structural Alignment Score, SAS:
<disp-formula id="Equ9"><label>9</label>
<alternatives><tex-math id="M77">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} SAS = 100 \frac{cRMS}{N}, \end{array} $$ \end{document}</tex-math>
<mml:math id="M78"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:mtext mathvariant="italic">SAS</mml:mtext>
<mml:mo>=</mml:mo>
<mml:mn>100</mml:mn>
<mml:mfrac><mml:mrow><mml:mtext mathvariant="italic">cRMS</mml:mtext>
</mml:mrow>
<mml:mrow><mml:mi>N</mml:mi>
</mml:mrow>
</mml:mfrac>
<mml:mo>,</mml:mo>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ9.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>originally introduced by the authors of STRUCTAL [<xref ref-type="bibr" rid="CR47">47</xref>
].</p>
</sec>
<sec id="Sec13"><title>Reproducibility</title>
<p>The program SeqKernel described above, as well as all the datasets of sequences used in this study are available from the authors upon request.</p>
</sec>
</sec>
<sec id="Sec14"><title>Results and Discussion</title>
<p>Two proteins with highly similar sequences almost always have similar structures. The reverse, however, is not always true. In a comprehensive analysis of the relationship between sequence similarity and structure similarity, Rost [<xref ref-type="bibr" rid="CR16">16</xref>
] has shown that pairs of proteins with similar structures possess, on average, only 8-10% sequence identity. This observation is at the root of the difficulties observed when attempting to classify proteins based on sequence information only. We have tested an alternative method to standard pairwise sequence comparison. We propose to use a string kernel that provides an alignment-free measure of the similarity of two protein sequences. We then use that measure to classify those protein sequences and compare the corresponding classification results with classifications derived from 3D structures and sequences only. Our aim is to parameterize the string kernel such that it performs better than sequence alignment based methods, mimicking to some extend the classifications derived from structure. We use CATH2833 and CATH793 as our main test sets. CATH2833 is a dataset of 2833 protein sequences that correspdond to the three main classes of CATH: one <italic>α</italic>
fold, one <italic>β</italic>
fold, and three <italic>α</italic>
/<italic>β</italic>
folds (see “<xref rid="Sec2" ref-type="sec">Methods</xref>
” section above). CATH2833 was designed in such a way that the sequences of any pair of proteins included have statistically no detectable similarity, by enforcing a FASTA [<xref ref-type="bibr" rid="CR43">43</xref>
] SSEARCH E-value >10<sup>−4</sup>
. CATH793 is a subset of CATH2833 that contains those proteins whose lengths are limited to a small range, from 120 to 180 amino acids.</p>
<sec id="Sec15"><title>Assessing the different protein sequence distances using receiver operator curve (ROC) analyses</title>
<p>ROC analysis of protein fold recognition based on FASTA E-values for pairwise sequence comparison, SAS scores for 3D structure comparison using STRUCTAL (see “<xref rid="Sec2" ref-type="sec">Methods</xref>
” above), and two conditions for the alignment-free SeqKernel comparisons are shown in panels a and b of Fig. <xref rid="Fig2" ref-type="fig">2</xref>
for the datasets CATH2833 and CATH793, respectively. These ROC analyses are based on averaged behaviors over the five folds included in those two datasets (i.e. a pair of sequences is considered to be positive if they belong to the same fold, independent of this fold. Results broken down by fold are given in Tables <xref rid="Tab2" ref-type="table">2</xref>
and <xref rid="Tab3" ref-type="table">3</xref>
for CATH2833 and CATH793, respectively.
<fig id="Fig2"><label>Fig. 2</label>
<caption><p>ROC analyses of three measures of protein similarity. We compare the efficiency of two sequence comparison methods, pairwise sequence alignment using SSEARCH from FASTA (<italic>red</italic>
), the SeqKernel alignment free method introduced in this paper with two sets of parameters, (<italic>k</italic>
<sub><italic>max</italic>
</sub>
=2, <italic>β</italic>
=0.0001) (<italic>green</italic>
), (<italic>k</italic>
<sub><italic>max</italic>
</sub>
=10, <italic>β</italic>
=0.2) (<italic>cyan</italic>
), and the 3D structure alignment program STRUCTAL (<italic>purple</italic>
) to detect fold similarity in two different sets of proteins, CATH2883 (panel <bold>a</bold>
), and CATH793 (panel <bold>b</bold>
). “True” relationships are defined according to CATH topologies. Curves close to the first diagonal (such as the ROC curve for FASTA) indicate poor performance, while the upper most curves (such as the 3D structure-based curve) indicate good performance</p>
</caption>
<graphic xlink:href="12859_2017_1560_Fig2_HTML" id="MO2"></graphic>
</fig>
<table-wrap id="Tab2"><label>Table 2</label>
<caption><p>Area Under the Curve (AUC) of ROC analyses for the FASTA, STRUCTAL, and SeqKernel distances for comparing protein sequences from CATH2833</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left"></th>
<th align="left" colspan="4">Distance</th>
<th align="left"></th>
</tr>
<tr><th align="left">CATH fold ID</th>
<th align="left">N <sup>a</sup>
</th>
<th align="left">FASTA <sup>b</sup>
</th>
<th align="left">STRUCTAL <sup>c</sup>
</th>
<th align="left">SeKernel(0.2,10) <sup>d</sup>
</th>
<th align="left">SeqKernel(0.0001,2) <sup>e</sup>
</th>
</tr>
</thead>
<tbody><tr><td align="left">1.10.10</td>
<td align="left">381</td>
<td align="left">0.58</td>
<td align="left">0.85</td>
<td align="left">0.31</td>
<td align="left">0.62</td>
</tr>
<tr><td align="left">2.60.40</td>
<td align="left">555</td>
<td align="left">0.58</td>
<td align="left">0.97</td>
<td align="left">0.38</td>
<td align="left">0.65</td>
</tr>
<tr><td align="left">3.20.20</td>
<td align="left">251</td>
<td align="left">0.53</td>
<td align="left">0.99</td>
<td align="left">0.88</td>
<td align="left">0.85</td>
</tr>
<tr><td align="left">3.30.70</td>
<td align="left">368</td>
<td align="left">0.53</td>
<td align="left">0.92</td>
<td align="left">0.33</td>
<td align="left">0.62</td>
</tr>
<tr><td align="left">3.40.50</td>
<td align="left">1278</td>
<td align="left">0.53</td>
<td align="left">0.92</td>
<td align="left">0.77</td>
<td align="left">0.77</td>
</tr>
<tr><td align="left">All five folds</td>
<td align="left">2833</td>
<td align="left">0.54</td>
<td align="left">0.93</td>
<td align="left">0.69</td>
<td align="left">0.76</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p><sup>a</sup>
Number of proteins in the fold</p>
<p><sup>b</sup>
AUC based on FASTA E-value</p>
<p><sup>c</sup>
AUC based on STRUCTAL SAS score</p>
<p><sup>d and e</sup>
AUC based on SeqKernel distance, with (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10) (d) and (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.0001,2) (e)</p>
</table-wrap-foot>
</table-wrap>
<table-wrap id="Tab3"><label>Table 3</label>
<caption><p>Area Under the Curve (AUC) of ROC analyses for the FASTA, STRUCTAL, and SeqKernel distances for comparing protein sequences from CATH793</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left"></th>
<th align="left" colspan="4">Distance</th>
<th align="left"></th>
</tr>
<tr><th align="left">CATH fold ID</th>
<th align="left">N <sup>a</sup>
</th>
<th align="left">FASTA <sup>b</sup>
</th>
<th align="left">STRUCTAL <sup>c</sup>
</th>
<th align="left">SeKernel(0.2,10) <sup>d</sup>
</th>
<th align="left">SeqKernel(0.0001,2) <sup>e</sup>
</th>
</tr>
</thead>
<tbody><tr><td align="left">1.10.10</td>
<td align="left">36</td>
<td align="left">0.75</td>
<td align="left">0.91</td>
<td align="left">0.61</td>
<td align="left">0.61</td>
</tr>
<tr><td align="left">2.60.40</td>
<td align="left">130</td>
<td align="left">0.55</td>
<td align="left">0.98</td>
<td align="left">0.44</td>
<td align="left">0.54</td>
</tr>
<tr><td align="left">3.30.70</td>
<td align="left">52</td>
<td align="left">0.51</td>
<td align="left">0.89</td>
<td align="left">0.45</td>
<td align="left">0.47</td>
</tr>
<tr><td align="left">3.40.50</td>
<td align="left">573</td>
<td align="left">0.57</td>
<td align="left">0.98</td>
<td align="left">0.69</td>
<td align="left">0.62</td>
</tr>
<tr><td align="left">All five folds</td>
<td align="left">791</td>
<td align="left">0.55</td>
<td align="left">0.98</td>
<td align="left">0.69</td>
<td align="left">0.62</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p><sup>a</sup>
Number of proteins in the fold</p>
<p><sup>b</sup>
AUC based on FASTA E-value</p>
<p><sup>c</sup>
AUC based on STRUCTAL SAS score</p>
<p><sup>d and e</sup>
AUC based on SeqKernel distance, with (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10) (d) and (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.0001,2) (e)</p>
</table-wrap-foot>
</table-wrap>
</p>
<p>The FASTA SSEARCH tool [<xref ref-type="bibr" rid="CR43">43</xref>
] is the implementation of a fast Smith and Waterman sequence comparison; it measures the similarity between two sequences either using directly the raw score of the alignment, or with a corresponding E-value. We have used the latter as a similarity measure. All SSEARCH alignments were performed using the BLOSUM62 substitution matrix [<xref ref-type="bibr" rid="CR42">42</xref>
], with gap penalties of -11 (opening) and -1 (extension). The ROC curves for this FASTA measure are marginally above the first diagonal, with AUC scores of 0.54 for both CATH2833 and CATH793. This behavior is expected, as by design all protein pairs in those datasets have little or no sequence similarity. The AUC values for the individual folds are very similar, ranging from 0.51 to 0.58, with one exception, fold 1.10.10 within the CATH793 dataset. We note however that this fold only contains 36 representatives in this dataset, making it the smallest set of all folds considered here. As such, this result is statistically unreliable.</p>
<p>Assignment of structural fold is expected to work best when it is based on 3D structural information. Indeed, the ROC curves obtained based on the SAS STRUCTAL scores illustrate excellent classification results, with AUC scores of 0.93 and 0.99 for CATH2833 and CATH793, respectively. We note that even with X-ray structure information the classification is not perfect, especially for CATH2833. This again is not a surprise. CATH is a semi-automatic classification of protein structures and some proteins are included in the same class based on more information than structure alone [<xref ref-type="bibr" rid="CR37">37</xref>
]. As such, two proteins may belong to the same class even though their structures are loosely similar. In addition, structural alignment programs work with heuristic algorithms and as such may miss the optimal alignment [<xref ref-type="bibr" rid="CR48">48</xref>
]. Finally, it is possible that a small fully <italic>α</italic>
or fully <italic>β</italic>
protein is found to be similar to an <italic>α</italic>
/<italic>β</italic>
protein, based on local alignment of the helical, or strand regions of the proteins. This is observed for example for proteins in fold 1.10.10 (the arc repressor all- <italic>α</italic>
fold), with an AUC of 0.85 for CATH2833. That said, STRUCTAL scores based on X-ray structures still perform remarkably well.</p>
<p>The ROC curves based on the alignment free sequence comparisons obtained with SeqKernel are intermediate between the FASTA and STRUCTAL curves, for the two sets of parameters considered. Clearly, kernel similarity measures improve the classification of proteins into folds, especially for those proteins whose sequences bear little similarity. This improvement is significant, from an overall AUC score of 0.54 for CATH2833 with FASTA to AUC values between 0.63 and 0.76 for CATH2833 with SeqKernel, depending on the values given to the parameters <italic>k</italic>
<sub><italic>max</italic>
</sub>
and <italic>β</italic>
. Similar improvements are observed for CATH793. Interestingly, the improvements between FASTA and SeqKernel are not consistent over all types of folds considered. SeqKernel performs significantly better for proteins in the <italic>α</italic>
−<italic>β</italic>
class (folds 3.20.20 and 3.40.50) than for the full <italic>α</italic>
fold (1.10.10) and for the full <italic>β</italic>
fold (2.60.40). Of similar interest, there is a discrepancy between the results obtained on CATH2833 and CATH793: for the former, a significantly better overall AUC is observed when the pair (<italic>k</italic>
<sub><italic>max</italic>
</sub>
,<italic>β</italic>
) is set to (2,0.0001), while for the latter, a better overall AUC is observed when the pair (<italic>k</italic>
<sub><italic>max</italic>
</sub>
,<italic>β</italic>
) is set to (10,0.2). In addition, results using (<italic>k</italic>
<sub><italic>max</italic>
</sub>
,<italic>β</italic>
)=(2,0.0001) are more consistent over the five folds considered. While differences are expected for different parameter values, the ranking of those parameter values is expected to remain the same on different datasets, especially here as CATH793 is a subset of CATH2833. This difference warrants a systematic study of the impact of the kernel parameters on its performance in fold recognition.</p>
</sec>
<sec id="Sec16"><title>Understanding the parameters <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
for the string kernel SeqKernel</title>
<p>The string kernel, SeqKernel, considered in this paper depends on two parameters, the coefficients <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
. <italic>β</italic>
is a power coefficient, i.e. it is used to compute the Hadamard power of the input substitution matrix <italic>SM</italic>
. As it is used in a Hadamard power, all strictly positive values for <italic>β</italic>
are possible, as the power matrix remains a Gram matrix. The parameter <italic>k</italic>
<sub><italic>max</italic>
</sub>
defines the longest <italic>k-mers</italic>
that are considered in the comparison of the two sequences. Note that the maximum value for <italic>k</italic>
<sub><italic>max</italic>
</sub>
is the size of the smallest sequence. Intuitively, using large values for <italic>k</italic>
<sub><italic>max</italic>
</sub>
are expected to help as the longer <italic>k-mers</italic>
capture correlations in the protein sequences. However, as described in the implementation section, large <italic>k</italic>
<sub><italic>max</italic>
</sub>
values come at a computational cost. We have tested a range of values for <italic>β</italic>
from very small, 10<sup>−5</sup>
, to relatively large, 1, and a range of values for <italic>k</italic>
<sub><italic>max</italic>
</sub>
, from 1 (i.e. single amino acid comparison) to 20. For pairs of values (<italic>β</italic>
, <italic>k</italic>
<sub><italic>max</italic>
</sub>
) taken from their respective ranges, we computed the similarity scores for all pairs of proteins in CATH2833 and CATH793, and assessed the ability of those scores for fold recognition using ROC analysis. The resulting AUC scores are reported in Fig. <xref rid="Fig3" ref-type="fig">3</xref>
. Note that the higher the AUC, the better the performance. In parallel, we also compared the string kernel similarity scores with the corresponding STRUCTAL SAS scores. As STRUCTAL was found to perform extremely well in the ROC analysis (see Fig. <xref rid="Fig2" ref-type="fig">2</xref>
), the SeqKernel similarity scores should mimic the SAS scores for good fold recognition. We therefore computed the Pearson’s correlation coefficient PCC between the two sets of values, i.e. similarity scores and SAS values, for all pairs of proteins that belong to the same folds. The resulting PCC values are also reported in Fig. <xref rid="Fig3" ref-type="fig">3</xref>
. Again, the higher the PCC, the better the performance.
<fig id="Fig3"><label>Fig. 3</label>
<caption><p>Parameterizing the string kernel SeqKernel. The string kernel defined in this paper is defined by two parameters, <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
(see text for details) We varied those two parameters in the respective ranges [10<sup>−5</sup>
,1] and [1,20]; for each corresponding pairs of values, we applied the corresponding kernel to compute the similarities of all pairs of proteins in CATH2833 and CATH793 and checked the rankings of these similarities with the CATH classification of the proteins, using a ROC analysis. The corresponding AUC values are reported in panels <bold>a</bold>
and <bold>b</bold>
, respectively. High values of AUC indicate better fold recognition. Notice the different behaviors on the two datasets (panel <bold>a</bold>
vs panel <bold>b</bold>
). In panel <bold>c</bold>
and <bold>d</bold>
, we report in parallel the Pearson’s correlation coefficients between the kernel similarity measures and the STRUCTAL SAS values, for all pairs of parameters considered. As we assess the performance of SeqKernel in fold recognition, the SeqKernel values are expected to mimic the SAS scores, and therefore the larger the correlation coefficient, the better the performance of SeqKernel</p>
</caption>
<graphic xlink:href="12859_2017_1560_Fig3_HTML" id="MO3"></graphic>
</fig>
</p>
<p>The results on the CATH2833 dataset show two different behaviors depending on the <italic>β</italic>
values: for very small <italic>β</italic>
values (below 10<sup>−3</sup>
), all the AUC=f(<italic>k</italic>
<sub><italic>max</italic>
</sub>
) curves reach the same plateau with a relatively high value of 0.76, while for larger values of <italic>β</italic>
(>0.1), the same curves behave similarly but reach different maxima, with the <italic>β</italic>
values corresponding to these maxima decreasing as <italic>k</italic>
<sub><italic>max</italic>
</sub>
increases. Interestingly, the results on the CATH793 dataset are very different: while the same behavior is observed for the large values of <italic>β</italic>
, SeqKernel provides poor fold recognition for very small <italic>β</italic>
values. The key difference between the two datasets is that the latter includes proteins that cover a very small range of lengths. The discrepancy in behavior therefore hints to SeqKernel being able to pick differences in protein lengths for small <italic>β</italic>
values. Indeed, as <italic>β</italic>
→0, all the values in the kernel <italic>K</italic>
<sub>1</sub>
tend to 1, and <italic>K</italic>
<sub>1</sub>
becomes a matrix of ones. While this matrix does not correspond to a kernel (it is not positive definite), it can still be used in practice as input to SeqKernel. Using this matrix, the semi-kernel <italic>K</italic>
<sub>3</sub>
can in fact be computed analytically:
<disp-formula id="Equ10"><label>10</label>
<alternatives><tex-math id="M79">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\begin{array}{@{}rcl@{}} K_{3}(S,T) = \sum_{k=1}^{k_{max}} (n-k+1)(m-k+1) \end{array} $$ \end{document}</tex-math>
<mml:math id="M80"><mml:mtable class="eqnarray" columnalign="left center right"><mml:mtr><mml:mtd class="eqnarray-1"><mml:msub><mml:mrow><mml:mi>K</mml:mi>
</mml:mrow>
<mml:mrow><mml:mn>3</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>(</mml:mo>
<mml:mi>S</mml:mi>
<mml:mo>,</mml:mo>
<mml:mi>T</mml:mi>
<mml:mo>)</mml:mo>
<mml:mo>=</mml:mo>
<mml:munderover><mml:mrow><mml:mo>∑</mml:mo>
</mml:mrow>
<mml:mrow><mml:mi>k</mml:mi>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
</mml:mrow>
<mml:mrow><mml:msub><mml:mrow><mml:mi>k</mml:mi>
</mml:mrow>
<mml:mrow><mml:mtext mathvariant="italic">max</mml:mtext>
</mml:mrow>
</mml:msub>
</mml:mrow>
</mml:munderover>
<mml:mo>(</mml:mo>
<mml:mi>n</mml:mi>
<mml:mo>−</mml:mo>
<mml:mi>k</mml:mi>
<mml:mo>+</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>)</mml:mo>
<mml:mo>(</mml:mo>
<mml:mi>m</mml:mi>
<mml:mo>−</mml:mo>
<mml:mi>k</mml:mi>
<mml:mo>+</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>)</mml:mo>
</mml:mtd>
</mml:mtr>
</mml:mtable>
</mml:math>
<graphic xlink:href="12859_2017_1560_Article_Equ10.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p>Using this semi-kernel, we found that it performs with an AUC of 0.76 on the classification of the proteins in CATH2833. This high value of 0.76 therefore only reflects the differences in the distribution of lengths of the proteins in the five folds. Those differences are significant, see Table <xref rid="Tab1" ref-type="table">1</xref>
. While an interesting observation by itself, this is not the string kernel we are interested in. Indeed, Eq. <xref rid="Equ10" ref-type="">10</xref>
shows that it is independent of the actual sequences themselves, and only captures length differences; for example, the corresponding correlation semi-kernel takes the value of 1 for all pairs of sequences of the same lengths. These results suggest to use a kernel based on larger values of <italic>β</italic>
. Figure <xref rid="Fig3" ref-type="fig">3</xref>
<xref rid="Fig3" ref-type="fig">a</xref>
and <xref rid="Fig3" ref-type="fig">b</xref>
indicate that any value of <italic>k</italic>
<sub><italic>max</italic>
</sub>
is possible, pending that the proper value for <italic>β</italic>
is chosen. We suggest using the pair (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10). Interestingly, the corresponding kernel leads to the same AUCs on the two datasets, CATH2833 and CATH793 (see above).</p>
<p>Comparisons of the kernel values with the STRUCTAL SAS values confirm this analysis, see panels c and d in Fig. <xref rid="Fig3" ref-type="fig">3</xref>
. The PCC values between these two measures are found low for small values of <italic>β</italic>
. In such conditions, the kernel was shown to mainly capture lengths, while the STRUCTAL scores are mostly independent of lengths. For larger values of <italic>β</italic>
, the PCC values reach maxima for the same pairs of values (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
) than the AUC values.</p>
</sec>
<sec id="Sec17"><title>Choosing the input substitution matrix</title>
<p>There is one other parameter that defines the string kernel SeqKernel, namely the input substitution matrix. We compared fold recognition performance as measured by ROC analysis of both FASTA and SeqKernel (with <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
set to 0.2 and 10, respectively) on the two datasets CATH2833 and CATH793 for different input substitution matrices. Results are shown in Fig. <xref rid="Fig4" ref-type="fig">4</xref>
. As a reminder, FASTA and SeqKernel use different matrices as input: FASTA uses a BLOSUM-like matrix, while SeqKernel uses its own count-based matrix. Those two matrices however are mathematically related by a simple <italic>log</italic>
function. We note that there are little variations in the performance of both FASTA and SeqKernel as we change their input matrices. More surprisingly, SeqKernel performs quite well with the Identity matrix as input. This indicates that at least for the two datasets considered here, a strict score that does not favor replacement is good enough for fold recognition.
<fig id="Fig4"><label>Fig. 4</label>
<caption><p>Choosing the substitution matrix. Comparison of the performances of FASTA and SeqKernel (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10), as measured by AUC values, for different input substitution matrices, namely the BLOSUM30 (BL30), BLOSUM62 (BL62), BLOSUM90 (BL90), and the Identity matrices. The two values for FASTA and for Seqkernel correspond to the two datasets CATH2833 and CATH793, respectively</p>
</caption>
<graphic xlink:href="12859_2017_1560_Fig4_HTML" id="MO4"></graphic>
</fig>
</p>
</sec>
<sec id="Sec18"><title>Protein fold classification</title>
<p>We extended the ROC analyses of our sequence similarity measures to assessing their performances for actual fold recognition by performing a set of computational fold classification experiments. Note that we are not interested in establishing a classification for a family of protein structures: rather, we are interested in testing the ability of distance measures based on sequences to assign a protein to the structural class it belongs to. We perform this test using a series of computational experiments. For those experiments, we consider all folds included in Cath40e4 with at list 40 members, excluding the five folds considered in CATH2833, to eliminate possible biases as SeqKernel was parametrized based on these folds. There are 40 such folds, for a total of 3744 proteins, which we refer to as CATH3744. We consider three levels of classifications for those proteins, as defined by CATH: the Class level (3 such classes, <italic>α</italic>
, <italic>β</italic>
, and mixed <italic>α</italic>
/<italic>β</italic>
, the Architecture level (13 such architectures, 3 in the <italic>α</italic>
class, 4 in the <italic>β</italic>
class, and 6 in the mixed <italic>α</italic>
/<italic>β</italic>
class), and at the Topology (or fold) level (40 such topologies, 10 in the <italic>α</italic>
class, 10 in the <italic>β</italic>
class, and 20 in the mixed <italic>α</italic>
/<italic>β</italic>
class). Each experiment starts with those proteins, and a choice for the classification level. We pick at random half of the proteins of each group at the level considered, and define them as the <italic>training set</italic>
. The remaining proteins form the <italic>test set</italic>
. The training set is used to define the groups for the distance-based classifiers (see “<xref rid="Sec2" ref-type="sec">Methods</xref>
” for details). The experiment then proceeds by assigning a group to each protein in the test set. A protein is considered successfully classified if it is assigned to its actual CATH group (C, A, or T, based on the experiment considered). Experiments are repeated 10,000 times and the results averaged to remove potential bias in the choice of proteins that define the folds.</p>
<p>For those fold classification experiments, we considered 8 possible distances between protein sequences. As a null reference, we assign a random value between 0 and 1 for the distance between two proteins. We call this distance RANDOM. On the other end of the spectrum, we include results based on the STRUCTAL SAS scores; those results directly reflect structural similarities. The third distance is based on the FASTA SSEARCH E-value. The fourth and fifth distances are computed with SeqKernel. As described in the previous section, there seem to be two regimes for SeqKernel, based on the values for the parameters <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
. We picked one example from each regime, setting (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
) to (0.0001,2) and (0.2,10), respectively. The last three distances are based on other string kernels for comparing strings. We considered the subsequence string kernel introduced by Lodhi <italic>et al</italic>
[<xref ref-type="bibr" rid="CR28">28</xref>
], Subseq, the Spectrum string kernel of Leslie <italic>et al</italic>
[<xref ref-type="bibr" rid="CR31">31</xref>
], and WDegree, the weighted string kernel of Rätsch and colleagues [<xref ref-type="bibr" rid="CR33">33</xref>
,<xref ref-type="bibr" rid="CR34">34</xref>
]. For those last kernel distances, we used the implementations provided in the package Harry [<xref ref-type="bibr" rid="CR49">49</xref>
,<xref ref-type="bibr" rid="CR50">50</xref>
], with default parameters. Results of the classification experiments are given in Fig. <xref rid="Fig5" ref-type="fig">5</xref>
.
<fig id="Fig5"><label>Fig. 5</label>
<caption><p>Classifying proteins in structural groups based on sequence-based distances. Three levels of structural classifications are considered, the C(lass), A(architecture), and T(opology) levels defined by CATH. Proteins are classified based on their shortest distance to a known group, where the distance is one of seven sequence-based distances between proteins, a RANDOM distance, a FASTA-based distance based on alignment, two distances based on the string kernel defined in this work, corresponding to two different parameter settings, (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10) and (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.0001,2), and three other string kernel distances, Subseq [<xref ref-type="bibr" rid="CR28">28</xref>
], Spectrum [<xref ref-type="bibr" rid="CR31">31</xref>
], and WDegree, a weighted string kernel [<xref ref-type="bibr" rid="CR33">33</xref>
,<xref ref-type="bibr" rid="CR34">34</xref>
]). We also include results based on the STRUCTAL SAS scores; those results include structural information and should only be considered for reference. The classification accuracy (y-axis, in %) is computed as the ratio of proteins correctly classified over the total number of test proteins (see text for details)</p>
</caption>
<graphic xlink:href="12859_2017_1560_Fig5_HTML" id="MO5"></graphic>
</fig>
</p>
<p>Results from the reference RANDOM distances are on par with what is expected from the numbers of groups at each level of classification considered: 31% at the C level (1/3≈33<italic>%</italic>
), 9% at the A level (1/13≈8<italic>%</italic>
), and 3% at the T level (1/40≈3<italic>%</italic>
). With no surprise, the results based on FASTA mirror those RANDOM results: as described above, there is no information in the FASTA distances by design. Also, without surprise, the classifications based on the STRUCTAL distances between structures are significantly more accurate than those based on sequence only. It is interesting however that even those results are far from perfect. At the C level for example, only 54% of the proteins are correctly classified. Most misclassification come from <italic>α</italic>
+<italic>β</italic>
proteins being classified as <italic>α</italic>
or <italic>β</italic>
proteins. This is not unexpected, as STRUCTAL performs a local structural alignment. The classifications obtained with SeqKernel with (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
) set to (0.2,10) are significantly more accurate than those observed with the other sequence-based distances, at least at the Architecture and Topology levels. This includes the results obtained with SeqKernel with (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
) set to (0.0001,2), confirming that a somewhat large value for <italic>β</italic>
is preferred. Interestingly, the Subseq and Spectrum string kernels perform better at the Class level. It is likely that those two kernels capture the amino acid compositions of the sequences, which have been shown to be good discriminants of the protein structural class (as defined by CATH) [<xref ref-type="bibr" rid="CR51">51</xref>
,<xref ref-type="bibr" rid="CR52">52</xref>
].</p>
</sec>
<sec id="Sec19"><title>Alignment-free phylogeny reconstruction</title>
<p>A large number of biological modeling methods depend on accurate (multiple) sequence alignments. Protein structure prediction is one of those methods; it relies heavily on fold recognition. In the previous sections, we covered the use of alignment free methods for performing this task, comparing our string kernel SeqKernel with alignment-based methods. Another important modeling task that relies on sequence alignment is phylogenetic tree inference, a critical step in evolutionary studies. The majority of methods that perform this task follow a two step process, with the construction of a multiple sequence alignment followed by statistical tree inference [<xref ref-type="bibr" rid="CR53">53</xref>
,<xref ref-type="bibr" rid="CR54">54</xref>
]. These methods, though widely used, have known limitations related to uncertainties in the multiple sequence alignment [<xref ref-type="bibr" rid="CR38">38</xref>
,<xref ref-type="bibr" rid="CR39">39</xref>
,<xref ref-type="bibr" rid="CR55">55</xref>
–<xref ref-type="bibr" rid="CR57">57</xref>
]. Among all the approaches recently developed to alleviate those limitations, we note the alignment-free methods based on analyses of <italic>k-mers</italic>
in the sequences that are compared [<xref ref-type="bibr" rid="CR39">39</xref>
,<xref ref-type="bibr" rid="CR40">40</xref>
,<xref ref-type="bibr" rid="CR58">58</xref>
,<xref ref-type="bibr" rid="CR59">59</xref>
]. As SeqKernel provides a mean to quantify the similarity between two sequences using such <italic>k-mers</italic>
, we tested it on a simple toy problem of phylogenetic tree inference originally described by Thorne and Kishino [<xref ref-type="bibr" rid="CR38">38</xref>
]. To illustrate their methods for computing evolutionary distances between protein sequences, they considered 10 sequences of the second largest RNA polymerase subunit. We have repeated their analysis on the same sequences. These sequences include two eukaryotic pol I sequences, two eukaryotic pol II sequences, two eukaryotic pol III sequences, two archaebacterial sequences, a eubacterial sequence, and a chloroplast sequence; they are defined in Table <xref rid="Tab4" ref-type="table">4</xref>
.
<table-wrap id="Tab4"><label>Table 4</label>
<caption><p>The ten RNA polymerases</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left">Abbreviation</th>
<th align="left">Protein</th>
<th align="left">Species</th>
<th align="left">Accession number</th>
<th align="left">Length</th>
</tr>
</thead>
<tbody><tr><td align="left">SC1</td>
<td align="left">RNA Pol I subunit RPA2</td>
<td align="left"><italic>Yeast</italic>
</td>
<td align="left">RPA2_YEAST</td>
<td align="left">1203</td>
</tr>
<tr><td align="left">DR1</td>
<td align="left">RNA Pol I subunit RPA2</td>
<td align="left"><italic>Drosophila megalonaster</italic>
</td>
<td align="left">RPA2_DROME</td>
<td align="left">1129</td>
</tr>
<tr><td align="left">SC2</td>
<td align="left">RNA Pol II subunit RPB2</td>
<td align="left"><italic>Yeast</italic>
</td>
<td align="left">RPB2_YEAST</td>
<td align="left">1203</td>
</tr>
<tr><td align="left">DR2</td>
<td align="left">RNA Pol II subunit RPB2</td>
<td align="left"><italic>Drosophila megalonaster</italic>
</td>
<td align="left">RPB2_DROME</td>
<td align="left">1129</td>
</tr>
<tr><td align="left">SC3</td>
<td align="left">RNA Pol III subunit RPC2</td>
<td align="left"><italic>Yeast</italic>
</td>
<td align="left">RPC2_YEAST</td>
<td align="left">1203</td>
</tr>
<tr><td align="left">DR3</td>
<td align="left">RNA Pol III subunit RPC2</td>
<td align="left"><italic>Drosophila megalonaster</italic>
</td>
<td align="left">RPC2_DROME</td>
<td align="left">1129</td>
</tr>
<tr><td align="left">SUL</td>
<td align="left">RNA Pol subunit <italic>β</italic>
</td>
<td align="left"><italic>Sulfolobus acidocoldarius</italic>
</td>
<td align="left">A0A0U3H235_9CREN</td>
<td align="left">1126</td>
</tr>
<tr><td align="left">MET</td>
<td align="left">RNA Pol subunit B’</td>
<td align="left"><italic>Methano-bacterium</italic>
</td>
<td align="left">RPOB1_METTW</td>
<td align="left">1123</td>
</tr>
<tr><td align="left"></td>
<td align="left"></td>
<td align="left"><italic>thermoautotrophicum</italic>
</td>
<td align="left"></td>
<td align="left"></td>
</tr>
<tr><td align="left">ESC</td>
<td align="left">RNA Pol subunit <italic>β</italic>
</td>
<td align="left"><italic>Escherichia coli</italic>
</td>
<td align="left">RPOB_ECOSE</td>
<td align="left">1342</td>
</tr>
<tr><td align="left">SPI</td>
<td align="left">Chloroplast RNA Pol subunit <italic>β</italic>
</td>
<td align="left"><italic>Spinacia oleracea</italic>
</td>
<td align="left">RPOB_SPIOL</td>
<td align="left">1070</td>
</tr>
</tbody>
</table>
</table-wrap>
</p>
<p>We considered 5 different distance matrices between those sequences. The first matrix is the original distance matrix proposed by Thorne and Kishino. The second matrix is derived from the multiple sequence alignment of those 10 sequences, computed with Clustal Omega [<xref ref-type="bibr" rid="CR60">60</xref>
], and converted into a distance matrix using the program ProtDist from the software package Phylip [<xref ref-type="bibr" rid="CR61">61</xref>
]. We used the Jones, Taylor and Thornton model of amino acid change [<xref ref-type="bibr" rid="CR62">62</xref>
] within ProtDist to compute the distances. The third matrix is based on the Bit scores of the sequence alignments generated by SSEARCH from FASTA, computed with Blosum62 as a substitution matrix and gap penalties of -11/-1 for opening/extension, respectively. The fourth and fifth matrices are derived from SeqKernel, with two settings for the parameters <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
, namely (0.0001,2) and (0.2,10). We have built trees based on those five distance matrices using the programs Fitch and Drawtree from the Phylip package [<xref ref-type="bibr" rid="CR61">61</xref>
]. Fitch is an implementation of the Fitch and Margoliash [<xref ref-type="bibr" rid="CR63">63</xref>
] method for constructing trees from a distance matrix under the “additive tree model”. In this model, the distance between two sequences is expected to be equal to the sum of branch lengths between the sequences on the tree. These five trees are shown in Fig. <xref rid="Fig6" ref-type="fig">6</xref>
.
<fig id="Fig6"><label>Fig. 6</label>
<caption><p>Inferred RNA polymerase phylogeny. Five different phylogenetic trees were constructed for a group of 10 RNA polymerases, using five different distance measures between their sequences: (<bold>a</bold>
) the original distances proposed by Thorne and Kishino [<xref ref-type="bibr" rid="CR38">38</xref>
], (<bold>b</bold>
) distances derived from a Multiple Sequence Alignment of the 10 sequences computed with Clustal Omega [<xref ref-type="bibr" rid="CR60">60</xref>
], (<bold>c</bold>
) the BIT distances from FASTA SSEARCH tools, and the distances computed with SeqKernel with two different settings, namely (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10) (<bold>d</bold>
) and (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.0001,2) (<bold>e</bold>
). Abbreviations for species names are provided in Table <xref rid="Tab4" ref-type="table">4</xref>
. Branches corresponding to eukaryotic sequences are colored red, those for archaebacterial sequences are shown in blue, and the eubacterial and chloroplast sequences are highlighted in orange and green, respectively</p>
</caption>
<graphic xlink:href="12859_2017_1560_Fig6_HTML" id="MO6"></graphic>
</fig>
</p>
<p>With the exception of the tree generated from the distance matrix derived from the SeqKernel distances with <italic>β</italic>
and <italic>k</italic>
<sub><italic>max</italic>
</sub>
set to (0.0001,2) the trees are qualitatively similar to each other. As the 10 sequences have approximately the same lengths, and as SeqKernel with a small value of <italic>β</italic>
basically captures differences in length, the exception is not surprising. This result however does reinforce our choice for (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
) to (0.2,10). To quantify the differences between the four remaining trees, we first scaled the distance matrices so that all distances ranged between 0 and 1, and then regenerated the trees. The resulting trees are then compared with the program TreeDist, implemented in the software package Phylip. TreeDist is based on the branch score distance of Kuhner and Felsenstein [<xref ref-type="bibr" rid="CR64">64</xref>
] to evaluate the similarity between two trees. We find that the distances between the original tree of Thorne and Kishino and the Clustal-based, FASTA-based, and SeqKernel-based trees are 0.3, 0.57, and 0.39, respectively. Note that the distance between the original tree and the SeqKernel-based tree when (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
) is set to (0.0001,2) is 0.99. While we cannot assess the meaning of the absolute values of these distances, and the significance of the differences between those values, we do notice that the original Thorne and Kishino tree resembles most the tree computed with the Clustal-based tree, and the tree computed with the method introduced here.</p>
</sec>
</sec>
<sec id="Sec20" sec-type="conclusion"><title>Conclusions</title>
<p>The amino acid sequence of a protein encodes for its structure and ultimately its function in a cell. As such, sequence comparison remains one of the core tools used in many modeling methods in molecular biology that handle problems such as protein fold recognition and phylogenetic tree inference. We have shown that a string kernel that captures the similarity of all <italic>k-mers</italic>
in two protein sequences provides an alignment-free method for fold recognition and phylogenetic tree reconstruction that performs well when its parameters have been selected appropriately. We refer to this string kernel as SeqKernel. It depends on two parameters, <italic>β</italic>
, a power coefficient that modulates the values of the input substitution matrix, and <italic>k</italic>
<sub><italic>max</italic>
</sub>
, the maximum lengths of <italic>k-mers</italic>
considered. We have performed a systematic analysis of the impact of those two parameters on the performance of SeqKernel in fold recognition experiments involving remote homologs. We have shown that on our test datasets, SeqKernel performs remarkably well for very small values of <italic>β</italic>
(<10<sup>−3</sup>
), independently of <italic>k</italic>
<sub><italic>max</italic>
</sub>
. With such small values of <italic>β</italic>
however, SeqKernel is basically tuned to capture the difference in lengths of proteins, which is not of interest for fold recognition. We have shown that for larger values of <italic>β</italic>
, there are pairs of values (<italic>β</italic>
, <italic>k</italic>
<sub><italic>max</italic>
</sub>
) that provide significant performance in fold recognition. We suggest to use the pair (<italic>β</italic>
,<italic>k</italic>
<sub><italic>max</italic>
</sub>
)=(0.2,10). Interestingly, in the first presentation of a kernel equivalent to SeqKernel [<xref ref-type="bibr" rid="CR36">36</xref>
], the authors advocate the use of <italic>k</italic>
<sub><italic>max</italic>
</sub>
=10, and referred to <italic>β</italic>
as a mysterious parameter that they fixed to 0.11, i.e. close to the value of 0.2 that we propose here.</p>
<p>SeqKernel, just like any alignment-based sequence comparison method, depends on a score matrix, also called substitution matrix. Such a matrix provides a quantitative measure of the similarities of amino acids. We have shown that SeqKernel is not sensitive to the choice of this score matrix, at least on the two datasets CATH2833 and CATH793 used in this study. We note however that most of the score matrices, such as the BLOSUM matrices considered in this study, have not been optimized for the purpose of fold recognition. There has already been attempts to perform such optimization [<xref ref-type="bibr" rid="CR65">65</xref>
, <xref ref-type="bibr" rid="CR66">66</xref>
]. In future studies, we will explore further the problem of defining an optimal score matrix within the context of SeqKernel.</p>
<p>This paper represents work in progress. It is dedicated to the understanding of the parameters that define the string kernel SeqKernel as well as to the illustration of its applications in fold recognition problems and phylogenetic tree inference. In the latter, we have only presented a small toy example to highlight that a alignment-free estimate of the distances between protein sequences can perform as well as a method based on multiple sequence alignment. Much work remains to be done before SeqKernel can become a commodity tool for sequence analysis. The scores computed with SeqKernel, while corresponding to a metric, do not include information on significance. The computing time for comparing two sequences using SeqKernel is high, suggesting that SeqKernel may not be used for large database searches. All the tests performed in this study were related to single domain proteins, or to specific domains within a protein. There is a need to expand the range of applications of SeqKernel to multi-domain proteins, as those are more the norm than single-domain proteins. Applications to phylogenomics need to be expanded and validated on a much larger scale. All those points will serve as research topics in our future studies.</p>
</sec>
</body>
<back><glossary><title>Abbreviations</title>
<def-list><def-item><term>AUC</term>
<def><p>Area under the curve</p>
</def>
</def-item>
<def-item><term>cRMS</term>
<def><p>Coordinate root mean square</p>
</def>
</def-item>
<def-item><term>ROC</term>
<def><p>Receiver operator curve</p>
</def>
</def-item>
</def-list>
</glossary>
<ack><title>Acknowledgements</title>
<p>None.</p>
<sec id="d29e4538"><title>Funding</title>
<p>Patrice Koehl acknowledges support from the Ministry of Education of Singapore through Grant Number: MOE2012-T3-1-008.</p>
</sec>
<sec id="d29e4543"><title>Availability of data and materials</title>
<p>The program SeqKernel described in the paper, as well as all the datasets of sequences used in this study are available from the authors upon request.</p>
</sec>
<sec id="d29e4548"><title>Authors’ contributions</title>
<p>PK conceived the study, including the methodological choices and the selection of proteins, and wrote the programs required for the analyses. SN performed the computational experiments and carried out the analyses of the results. SN and PK wrote the paper as well as its subsequent revisions. All authors read and approved the final manuscript.</p>
</sec>
<sec id="d29e4553"><title>Competing interests</title>
<p>The authors declare that they have no competing interests.</p>
</sec>
<sec id="d29e4558"><title>Consent for publication</title>
<p>Not applicable.</p>
</sec>
<sec id="d29e4563"><title>Ethics approval and consent to participate</title>
<p>Not applicable.</p>
</sec>
</ack>
<ref-list id="Bib1"><title>References</title>
<ref id="CR1"><label>1</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Oldfield</surname>
<given-names>CJ</given-names>
</name>
<name><surname>Dunker</surname>
<given-names>AK</given-names>
</name>
</person-group>
<article-title>Intrinsically Disordered Proteins and Intrinsically Disordered Protein Regions</article-title>
<source>Ann Rev Biochem</source>
<year>2014</year>
<volume>83</volume>
<fpage>553</fpage>
<lpage>84</lpage>
<pub-id pub-id-type="doi">10.1146/annurev-biochem-072711-164947</pub-id>
<pub-id pub-id-type="pmid">24606139</pub-id>
</element-citation>
</ref>
<ref id="CR2"><label>2</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Dill</surname>
<given-names>KA</given-names>
</name>
<name><surname>Ozkan</surname>
<given-names>SB</given-names>
</name>
<name><surname>Weikl</surname>
<given-names>TR</given-names>
</name>
<name><surname>Chodera</surname>
<given-names>JD</given-names>
</name>
<name><surname>Voelz</surname>
<given-names>VA</given-names>
</name>
</person-group>
<article-title>The protein folding problem: when will it be solved?</article-title>
<source>Curr Opin Struct Biol</source>
<year>2007</year>
<volume>17</volume>
<fpage>342</fpage>
<lpage>6</lpage>
<pub-id pub-id-type="doi">10.1016/j.sbi.2007.06.001</pub-id>
<pub-id pub-id-type="pmid">17572080</pub-id>
</element-citation>
</ref>
<ref id="CR3"><label>3</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Das</surname>
<given-names>R</given-names>
</name>
<name><surname>Baker</surname>
<given-names>D</given-names>
</name>
</person-group>
<article-title>Macromolecular modeling with Rosetta</article-title>
<source>Annu Rev Biochem</source>
<year>2008</year>
<volume>77</volume>
<fpage>363</fpage>
<lpage>82</lpage>
<pub-id pub-id-type="doi">10.1146/annurev.biochem.77.062906.171838</pub-id>
<pub-id pub-id-type="pmid">18410248</pub-id>
</element-citation>
</ref>
<ref id="CR4"><label>4</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Bairoch</surname>
<given-names>A</given-names>
</name>
<name><surname>Apweiler</surname>
<given-names>R</given-names>
</name>
</person-group>
<article-title>The Swiss-Prot protein sequence data bank and its supplement TrEMBL in</article-title>
<source>Nucl Acids Res</source>
<year>2000</year>
<volume>28</volume>
<fpage>45</fpage>
<lpage>8</lpage>
<pub-id pub-id-type="doi">10.1093/nar/28.1.45</pub-id>
<pub-id pub-id-type="pmid">10592178</pub-id>
</element-citation>
</ref>
<ref id="CR5"><label>5</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Berman</surname>
<given-names>HM</given-names>
</name>
<name><surname>Westbrook</surname>
<given-names>J</given-names>
</name>
<name><surname>Feng</surname>
<given-names>Z</given-names>
</name>
<name><surname>Gilliland</surname>
<given-names>G</given-names>
</name>
<name><surname>Bhat</surname>
<given-names>TN</given-names>
</name>
<name><surname>Weissig</surname>
<given-names>H</given-names>
</name>
<etal></etal>
</person-group>
<article-title>The Protein Data Bank</article-title>
<source>Nucl Acids Res</source>
<year>2000</year>
<volume>28</volume>
<fpage>235</fpage>
<lpage>42</lpage>
<pub-id pub-id-type="doi">10.1093/nar/28.1.235</pub-id>
<pub-id pub-id-type="pmid">10592235</pub-id>
</element-citation>
</ref>
<ref id="CR6"><label>6</label>
<mixed-citation publication-type="other">The Uniprot Consortium. UniProt: a hub for protein information. Nucl Acids Res. 2015; 43:D204–D212.</mixed-citation>
</ref>
<ref id="CR7"><label>7</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Waterman</surname>
<given-names>MS</given-names>
</name>
</person-group>
<source>Introduction to computational biology: maps, sequences, and genomes</source>
<year>1995</year>
<publisher-loc>Boca Raton</publisher-loc>
<publisher-name>Chapman and Hall / CRC Interdisciplinary Statistics</publisher-name>
</element-citation>
</ref>
<ref id="CR8"><label>8</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Durbin</surname>
<given-names>R</given-names>
</name>
<name><surname>Eddy</surname>
<given-names>SR</given-names>
</name>
<name><surname>Krogh</surname>
<given-names>A</given-names>
</name>
<name><surname>Mitchison</surname>
<given-names>G</given-names>
</name>
</person-group>
<source>Biological sequence analysis: probabilistic models of nucleic acids and proteins</source>
<year>1998</year>
<publisher-loc>New York</publisher-loc>
<publisher-name>Cambridge University Press</publisher-name>
</element-citation>
</ref>
<ref id="CR9"><label>9</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Gusfield</surname>
<given-names>D</given-names>
</name>
</person-group>
<source>Algorithms on strings, trees, and sequences: computer science and computational biology</source>
<year>1997</year>
<publisher-loc>New York</publisher-loc>
<publisher-name>Cambridge University Press</publisher-name>
</element-citation>
</ref>
<ref id="CR10"><label>10</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Schwartz</surname>
<given-names>RM</given-names>
</name>
<name><surname>Dayhoff</surname>
<given-names>MO</given-names>
</name>
</person-group>
<article-title>Matrices for detecting distant relationships</article-title>
<source>Atlas of Protein Sequence and Structure</source>
<year>1978</year>
<volume>5</volume>
<fpage>345</fpage>
<lpage>52</lpage>
</element-citation>
</ref>
<ref id="CR11"><label>11</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Henikoff</surname>
<given-names>S</given-names>
</name>
<name><surname>Henikoff</surname>
<given-names>JG</given-names>
</name>
</person-group>
<article-title>Amino acid substitution matrices</article-title>
<source>Adv Protein Chem</source>
<year>2000</year>
<volume>54</volume>
<fpage>73</fpage>
<lpage>97</lpage>
<pub-id pub-id-type="doi">10.1016/S0065-3233(00)54003-0</pub-id>
<pub-id pub-id-type="pmid">10829225</pub-id>
</element-citation>
</ref>
<ref id="CR12"><label>12</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ladunga</surname>
<given-names>I</given-names>
</name>
</person-group>
<article-title>PHYSEAN: PHYsical SEquence ANalysis for the identification of protein domains on the basis of physical and chemical properties of amino acids</article-title>
<source>Bioinformatics</source>
<year>1999</year>
<volume>15</volume>
<fpage>1028</fpage>
<lpage>38</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/15.12.1028</pub-id>
<pub-id pub-id-type="pmid">10745993</pub-id>
</element-citation>
</ref>
<ref id="CR13"><label>13</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Smith</surname>
<given-names>TF</given-names>
</name>
<name><surname>Waterman</surname>
<given-names>MS</given-names>
</name>
</person-group>
<article-title>Identification of Common Molecular Subsequences</article-title>
<source>J Mol Biol</source>
<year>1981</year>
<volume>147</volume>
<fpage>195</fpage>
<lpage>7</lpage>
<pub-id pub-id-type="doi">10.1016/0022-2836(81)90087-5</pub-id>
<pub-id pub-id-type="pmid">7265238</pub-id>
</element-citation>
</ref>
<ref id="CR14"><label>14</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Needleman</surname>
<given-names>SB</given-names>
</name>
<name><surname>Wunsch</surname>
<given-names>CD</given-names>
</name>
</person-group>
<article-title>A general method applicable to the search for similarities in the amino acid sequence of two proteins</article-title>
<source>J Mol Biol</source>
<year>1970</year>
<volume>48</volume>
<fpage>443</fpage>
<lpage>53</lpage>
<pub-id pub-id-type="doi">10.1016/0022-2836(70)90057-4</pub-id>
<pub-id pub-id-type="pmid">5420325</pub-id>
</element-citation>
</ref>
<ref id="CR15"><label>15</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Storey</surname>
<given-names>JD</given-names>
</name>
<name><surname>Sigmund</surname>
<given-names>D</given-names>
</name>
</person-group>
<article-title>Approximate p-values for local sequence alignments: numerical studies</article-title>
<source>J Comput Biol</source>
<year>2001</year>
<volume>8</volume>
<fpage>549</fpage>
<lpage>56</lpage>
<pub-id pub-id-type="doi">10.1089/106652701753216530</pub-id>
<pub-id pub-id-type="pmid">11694182</pub-id>
</element-citation>
</ref>
<ref id="CR16"><label>16</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Rost</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>Twilight zone for sequence alignment</article-title>
<source>Protein Eng</source>
<year>1999</year>
<volume>12</volume>
<fpage>85</fpage>
<lpage>94</lpage>
<pub-id pub-id-type="doi">10.1093/protein/12.2.85</pub-id>
<pub-id pub-id-type="pmid">10195279</pub-id>
</element-citation>
</ref>
<ref id="CR17"><label>17</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Wallace</surname>
<given-names>IM</given-names>
</name>
<name><surname>Blackshields</surname>
<given-names>G</given-names>
</name>
<name><surname>Higgins</surname>
<given-names>DG</given-names>
</name>
</person-group>
<article-title>Multiple sequence alignments</article-title>
<source>Curr Opin Struct Biol</source>
<year>2005</year>
<volume>15</volume>
<fpage>261</fpage>
<lpage>6</lpage>
<pub-id pub-id-type="doi">10.1016/j.sbi.2005.04.002</pub-id>
<pub-id pub-id-type="pmid">15963889</pub-id>
</element-citation>
</ref>
<ref id="CR18"><label>18</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Vinga</surname>
<given-names>S</given-names>
</name>
<name><surname>Almeida</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>Alignment-free sequence comparison–a review</article-title>
<source>Bioinformatics</source>
<year>2003</year>
<volume>19</volume>
<fpage>513</fpage>
<lpage>23</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btg005</pub-id>
<pub-id pub-id-type="pmid">12611807</pub-id>
</element-citation>
</ref>
<ref id="CR19"><label>19</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Bonham-Carter</surname>
<given-names>O</given-names>
</name>
<name><surname>Steele</surname>
<given-names>J</given-names>
</name>
<name><surname>Bastola</surname>
<given-names>D</given-names>
</name>
</person-group>
<article-title>Alignment–free genetic sequence comparisons: a review of recent approaches by word analysis</article-title>
<source>Brief Bioinform</source>
<year>2014</year>
<volume>15</volume>
<fpage>890</fpage>
<lpage>915</lpage>
<pub-id pub-id-type="doi">10.1093/bib/bbt052</pub-id>
<pub-id pub-id-type="pmid">23904502</pub-id>
</element-citation>
</ref>
<ref id="CR20"><label>20</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Vinga</surname>
<given-names>S</given-names>
</name>
</person-group>
<article-title>Alignment-free methods in computational biology</article-title>
<source>Brief Bioinform</source>
<year>2014</year>
<volume>15</volume>
<fpage>341</fpage>
<lpage>2</lpage>
<pub-id pub-id-type="doi">10.1093/bib/bbu005</pub-id>
<pub-id pub-id-type="pmid">24819825</pub-id>
</element-citation>
</ref>
<ref id="CR21"><label>21</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Schwende</surname>
<given-names>I</given-names>
</name>
<name><surname>Pham</surname>
<given-names>TD</given-names>
</name>
</person-group>
<article-title>Pattern recognition and probabilistic measures in alignment–free sequence analysis</article-title>
<source>Brief Bioinform</source>
<year>2014</year>
<volume>15</volume>
<fpage>354</fpage>
<lpage>68</lpage>
<pub-id pub-id-type="doi">10.1093/bib/bbt070</pub-id>
<pub-id pub-id-type="pmid">24096012</pub-id>
</element-citation>
</ref>
<ref id="CR22"><label>22</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ulitsky</surname>
<given-names>I</given-names>
</name>
<name><surname>Burstein</surname>
<given-names>D</given-names>
</name>
<name><surname>Tuller</surname>
<given-names>T</given-names>
</name>
<name><surname>Chor</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>The average common substring approach to phylogenic reconstruction</article-title>
<source>J Comput Biol</source>
<year>2006</year>
<volume>13</volume>
<fpage>336</fpage>
<lpage>50</lpage>
<pub-id pub-id-type="doi">10.1089/cmb.2006.13.336</pub-id>
<pub-id pub-id-type="pmid">16597244</pub-id>
</element-citation>
</ref>
<ref id="CR23"><label>23</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Didier</surname>
<given-names>G</given-names>
</name>
<name><surname>Corel</surname>
<given-names>E</given-names>
</name>
<name><surname>Laprevotte</surname>
<given-names>I</given-names>
</name>
<name><surname>Grossmann</surname>
<given-names>A</given-names>
</name>
<name><surname>Landes-Devauchelle</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>Variable length decoding and alignment–free sequence comparison</article-title>
<source>Theor Comput Sci</source>
<year>2012</year>
<volume>462</volume>
<fpage>1</fpage>
<lpage>11</lpage>
<pub-id pub-id-type="doi">10.1016/j.tcs.2012.08.005</pub-id>
</element-citation>
</ref>
<ref id="CR24"><label>24</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ma</surname>
<given-names>B</given-names>
</name>
<name><surname>Tromp</surname>
<given-names>J</given-names>
</name>
<name><surname>Li</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>PatternHunter: faster and more sensitive homology search</article-title>
<source>Bioinformatics</source>
<year>2002</year>
<volume>18</volume>
<fpage>440</fpage>
<lpage>5</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/18.3.440</pub-id>
<pub-id pub-id-type="pmid">11934743</pub-id>
</element-citation>
</ref>
<ref id="CR25"><label>25</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Burkhardt</surname>
<given-names>S</given-names>
</name>
<name><surname>Kärkkäinen</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>Better filtering with gapped q-grams</article-title>
<source>Fundam Inf</source>
<year>2003</year>
<volume>56</volume>
<fpage>51</fpage>
<lpage>70</lpage>
</element-citation>
</ref>
<ref id="CR26"><label>26</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Keich</surname>
<given-names>U</given-names>
</name>
<name><surname>Li</surname>
<given-names>M</given-names>
</name>
<name><surname>Ma</surname>
<given-names>B</given-names>
</name>
<name><surname>Tromp</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>On spaced seeds for similarity search</article-title>
<source>Discrete Appl Math</source>
<year>2004</year>
<volume>138</volume>
<fpage>253</fpage>
<lpage>63</lpage>
<pub-id pub-id-type="doi">10.1016/S0166-218X(03)00382-2</pub-id>
</element-citation>
</ref>
<ref id="CR27"><label>27</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Leimeister</surname>
<given-names>CA</given-names>
</name>
<name><surname>Boden</surname>
<given-names>M</given-names>
</name>
<name><surname>Horwege</surname>
<given-names>S</given-names>
</name>
<name><surname>Lindner</surname>
<given-names>S</given-names>
</name>
<name><surname>Morgenstern</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>Fast alignment-free sequence comparison using spaced-word frequencies</article-title>
<source>Bioinformatics</source>
<year>2014</year>
<volume>15</volume>
<fpage>1991</fpage>
<lpage>9</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btu177</pub-id>
</element-citation>
</ref>
<ref id="CR28"><label>28</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Lodhi</surname>
<given-names>H</given-names>
</name>
<name><surname>Saunders</surname>
<given-names>C</given-names>
</name>
<name><surname>Shawe-Taylor</surname>
<given-names>J</given-names>
</name>
<name><surname>Cristianini</surname>
<given-names>N</given-names>
</name>
<name><surname>Watkins</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>Text classification using string kernels</article-title>
<source>J Mach Learn Res</source>
<year>2002</year>
<volume>2</volume>
<fpage>419</fpage>
<lpage>44</lpage>
</element-citation>
</ref>
<ref id="CR29"><label>29</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Diekhans</surname>
<given-names>TJM</given-names>
</name>
<name><surname>Haussler</surname>
<given-names>D</given-names>
</name>
</person-group>
<article-title>A discriminative framework for detecting remote protein homologies</article-title>
<source>J Comput Biol</source>
<year>2000</year>
<volume>7</volume>
<fpage>95</fpage>
<lpage>114</lpage>
<pub-id pub-id-type="doi">10.1089/10665270050081405</pub-id>
<pub-id pub-id-type="pmid">10890390</pub-id>
</element-citation>
</ref>
<ref id="CR30"><label>30</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Liao</surname>
<given-names>L</given-names>
</name>
<name><surname>Noble</surname>
<given-names>WS</given-names>
</name>
</person-group>
<article-title>Combining pairwise sequence similarity and support vector machines for detecting remote protein evolutionary and structural relationships</article-title>
<source>J Comput Biol</source>
<year>2003</year>
<volume>10</volume>
<fpage>857</fpage>
<lpage>68</lpage>
<pub-id pub-id-type="doi">10.1089/106652703322756113</pub-id>
<pub-id pub-id-type="pmid">14980014</pub-id>
</element-citation>
</ref>
<ref id="CR31"><label>31</label>
<mixed-citation publication-type="other">Leslie C, Eskin E, Noble WS. The spectrum kernel: A string kernel for SVM protein clasSee sification In: Altman RB, Dunker AK, Hunter L, Lauderdale K, Klein TE, editors. Proceedings of the Pacific Symposium on Biocomputing: Kaua’i: 2002. p. 564–75.</mixed-citation>
</ref>
<ref id="CR32"><label>32</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Leslie</surname>
<given-names>CS</given-names>
</name>
<name><surname>Eskin</surname>
<given-names>E</given-names>
</name>
<name><surname>Cohen</surname>
<given-names>A</given-names>
</name>
<name><surname>Weston</surname>
<given-names>J</given-names>
</name>
<name><surname>Noble</surname>
<given-names>WS</given-names>
</name>
</person-group>
<article-title>Mismatch string kernels for discriminative protein classification</article-title>
<source>Bioinformatics</source>
<year>2004</year>
<volume>20</volume>
<fpage>467</fpage>
<lpage>76</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btg431</pub-id>
<pub-id pub-id-type="pmid">14990442</pub-id>
</element-citation>
</ref>
<ref id="CR33"><label>33</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Rätsch</surname>
<given-names>G</given-names>
</name>
<name><surname>Sonnenburg</surname>
<given-names>S</given-names>
</name>
<name><surname>Schölkopf</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>RASE: Recognition of alternatively spliced exons in C. elegans</article-title>
<source>Bioinformatics</source>
<year>2005</year>
<volume>21</volume>
<fpage>i369</fpage>
<lpage>i377</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/bti1053</pub-id>
<pub-id pub-id-type="pmid">15961480</pub-id>
</element-citation>
</ref>
<ref id="CR34"><label>34</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ben-Hur</surname>
<given-names>A</given-names>
</name>
<name><surname>Ong</surname>
<given-names>CS</given-names>
</name>
<name><surname>Sonnenburg</surname>
<given-names>S</given-names>
</name>
<name><surname>Schölkopf</surname>
<given-names>B</given-names>
</name>
<name><surname>Rätsch</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Support Vector Machines and Kernels for Computational Biology</article-title>
<source>PLOS Comput Biol</source>
<year>2008</year>
<volume>4</volume>
<fpage>e1000173</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pcbi.1000173</pub-id>
<pub-id pub-id-type="pmid">18974822</pub-id>
</element-citation>
</ref>
<ref id="CR35"><label>35</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Saigo</surname>
<given-names>H</given-names>
</name>
<name><surname>Vert</surname>
<given-names>JP</given-names>
</name>
<name><surname>Ueda</surname>
<given-names>N</given-names>
</name>
<name><surname>Akutsu</surname>
<given-names>T</given-names>
</name>
</person-group>
<article-title>Protein homology detection using string alignment kernels</article-title>
<source>Bioinformatics</source>
<year>2004</year>
<volume>20</volume>
<fpage>1682</fpage>
<lpage>9</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/bth141</pub-id>
<pub-id pub-id-type="pmid">14988126</pub-id>
</element-citation>
</ref>
<ref id="CR36"><label>36</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Shen</surname>
<given-names>WJ</given-names>
</name>
<name><surname>Wong</surname>
<given-names>HS</given-names>
</name>
<name><surname>Xiao</surname>
<given-names>QW</given-names>
</name>
<name><surname>Guo</surname>
<given-names>X</given-names>
</name>
<name><surname>Smale</surname>
<given-names>S</given-names>
</name>
</person-group>
<article-title>Introduction to the Peptide Binding Problem of Computational Immunology: New Results</article-title>
<source>Found Comput Math</source>
<year>2013</year>
<volume>14</volume>
<fpage>951</fpage>
<lpage>84</lpage>
<pub-id pub-id-type="doi">10.1007/s10208-013-9173-9</pub-id>
</element-citation>
</ref>
<ref id="CR37"><label>37</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Sillitoe</surname>
<given-names>I</given-names>
</name>
<name><surname>Lewis</surname>
<given-names>TE</given-names>
</name>
<name><surname>Cuff</surname>
<given-names>AL</given-names>
</name>
<name><surname>Das</surname>
<given-names>S</given-names>
</name>
<name><surname>Ashford</surname>
<given-names>P</given-names>
</name>
<name><surname>Dawson</surname>
<given-names>NL</given-names>
</name>
<etal></etal>
</person-group>
<article-title>CATH: comprehensive structural and functional annotations for genome sequences</article-title>
<source>Nucl Acids Res</source>
<year>2015</year>
<volume>43</volume>
<fpage>D376</fpage>
<lpage>D381</lpage>
<pub-id pub-id-type="doi">10.1093/nar/gku947</pub-id>
<pub-id pub-id-type="pmid">25348408</pub-id>
</element-citation>
</ref>
<ref id="CR38"><label>38</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Thorne</surname>
<given-names>JL</given-names>
</name>
<name><surname>Kishino</surname>
<given-names>H</given-names>
</name>
</person-group>
<article-title>Freeing phylogenies from artifacts of alignment</article-title>
<source>Mol Biol Evol</source>
<year>1992</year>
<volume>9</volume>
<fpage>1148</fpage>
<lpage>62</lpage>
<pub-id pub-id-type="pmid">1435239</pub-id>
</element-citation>
</ref>
<ref id="CR39"><label>39</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Chan</surname>
<given-names>CX</given-names>
</name>
<name><surname>Ragan</surname>
<given-names>MA</given-names>
</name>
</person-group>
<article-title>Next-generation phylogenomics</article-title>
<source>Biology direct</source>
<year>2013</year>
<volume>8</volume>
<fpage>3</fpage>
<pub-id pub-id-type="doi">10.1186/1745-6150-8-3</pub-id>
<pub-id pub-id-type="pmid">23339707</pub-id>
</element-citation>
</ref>
<ref id="CR40"><label>40</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Chan</surname>
<given-names>CX</given-names>
</name>
<name><surname>Bernard</surname>
<given-names>G</given-names>
</name>
<name><surname>Poirion</surname>
<given-names>O</given-names>
</name>
<name><surname>Hogan</surname>
<given-names>JM</given-names>
</name>
<name><surname>Ragan</surname>
<given-names>MA</given-names>
</name>
</person-group>
<article-title>Inferring phylogenies of evolving sequences without multiple sequence alignment</article-title>
<source>Scientific Reports</source>
<year>2014</year>
<volume>4</volume>
<fpage>6504</fpage>
<pub-id pub-id-type="doi">10.1038/srep06504</pub-id>
<pub-id pub-id-type="pmid">25266120</pub-id>
</element-citation>
</ref>
<ref id="CR41"><label>41</label>
<mixed-citation publication-type="other">Haussler D. Convolution Kernels on Discrete Structures: University of California, Santa Cruz; 1999. UCS-CRL-99-10.</mixed-citation>
</ref>
<ref id="CR42"><label>42</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Henikoff</surname>
<given-names>S</given-names>
</name>
<name><surname>Henikoff</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>Amino Acid Substitution Matrices from Protein Blocks</article-title>
<source>Proc Natl Acad Sci (USA)</source>
<year>1992</year>
<volume>89</volume>
<fpage>10915</fpage>
<lpage>9</lpage>
<pub-id pub-id-type="doi">10.1073/pnas.89.22.10915</pub-id>
<pub-id pub-id-type="pmid">1438297</pub-id>
</element-citation>
</ref>
<ref id="CR43"><label>43</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Pearson</surname>
<given-names>W</given-names>
</name>
<name><surname>Lipman</surname>
<given-names>D</given-names>
</name>
</person-group>
<article-title>Improved tools for biological sequence comparison</article-title>
<source>Proc Natl Acad Sci (USA)</source>
<year>1988</year>
<volume>85</volume>
<fpage>2444</fpage>
<lpage>8</lpage>
<pub-id pub-id-type="doi">10.1073/pnas.85.8.2444</pub-id>
<pub-id pub-id-type="pmid">3162770</pub-id>
</element-citation>
</ref>
<ref id="CR44"><label>44</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Le</surname>
<given-names>Q</given-names>
</name>
<name><surname>Pollastri</surname>
<given-names>G</given-names>
</name>
<name><surname>Koehl</surname>
<given-names>P</given-names>
</name>
</person-group>
<article-title>Structural Alphabets for Protein Structure Classification: A Comparison Study</article-title>
<source>J Mol Biol</source>
<year>2009</year>
<volume>387</volume>
<fpage>431</fpage>
<lpage>50</lpage>
<pub-id pub-id-type="doi">10.1016/j.jmb.2008.12.044</pub-id>
<pub-id pub-id-type="pmid">19135454</pub-id>
</element-citation>
</ref>
<ref id="CR45"><label>45</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Li</surname>
<given-names>J</given-names>
</name>
<name><surname>Koehl</surname>
<given-names>P</given-names>
</name>
</person-group>
<article-title>3D representations of amino acids - applications to protein sequence comparison and classification</article-title>
<source>Comp Struct Biotech J</source>
<year>2014</year>
<volume>11</volume>
<fpage>47</fpage>
<lpage>58</lpage>
<pub-id pub-id-type="doi">10.1016/j.csbj.2014.09.001</pub-id>
</element-citation>
</ref>
<ref id="CR46"><label>46</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Gribskov</surname>
<given-names>M</given-names>
</name>
<name><surname>Robinson</surname>
<given-names>NL</given-names>
</name>
</person-group>
<article-title>Use of receiver operating characteristic (ROC) analysis to evaluate sequence matching</article-title>
<source>Comput Chem</source>
<year>1996</year>
<volume>20</volume>
<fpage>25</fpage>
<lpage>33</lpage>
<pub-id pub-id-type="doi">10.1016/S0097-8485(96)80004-0</pub-id>
<pub-id pub-id-type="pmid">16718863</pub-id>
</element-citation>
</ref>
<ref id="CR47"><label>47</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Subbiah</surname>
<given-names>S</given-names>
</name>
<name><surname>Laurents</surname>
<given-names>DV</given-names>
</name>
<name><surname>Levitt</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Structural similarity of DNA-binding domains of bacteriophage repressors and the globin fold</article-title>
<source>Curr Biol</source>
<year>1993</year>
<volume>3</volume>
<fpage>141</fpage>
<lpage>8</lpage>
<pub-id pub-id-type="doi">10.1016/0960-9822(93)90255-M</pub-id>
<pub-id pub-id-type="pmid">15335781</pub-id>
</element-citation>
</ref>
<ref id="CR48"><label>48</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kolodny</surname>
<given-names>R</given-names>
</name>
<name><surname>Koehl</surname>
<given-names>P</given-names>
</name>
<name><surname>Levitt</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Comprehensive evaluation of protein structure alignment methods: scoring by geometric measures</article-title>
<source>J Mol Biol</source>
<year>2005</year>
<volume>346</volume>
<fpage>1173</fpage>
<lpage>88</lpage>
<pub-id pub-id-type="doi">10.1016/j.jmb.2004.12.032</pub-id>
<pub-id pub-id-type="pmid">15701525</pub-id>
</element-citation>
</ref>
<ref id="CR49"><label>49</label>
<mixed-citation publication-type="other">Rieck K. Similarity measures for sequential data. WIREs: Data Mininf and Knowledge Discovery. 2011; 1:296–304.</mixed-citation>
</ref>
<ref id="CR50"><label>50</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Rieck</surname>
<given-names>K</given-names>
</name>
<name><surname>Wresnegger</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>Harry: a tool for measuring string similarity</article-title>
<source>J Mach Learn Res</source>
<year>2016</year>
<volume>17</volume>
<fpage>1</fpage>
<lpage>5</lpage>
</element-citation>
</ref>
<ref id="CR51"><label>51</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Chou</surname>
<given-names>KC</given-names>
</name>
</person-group>
<article-title>A novel approach to predicting protein structural classes in a (20-1)-D amino acid composition space</article-title>
<source>Proteins: Struct Func Genet</source>
<year>1995</year>
<volume>21</volume>
<fpage>319</fpage>
<lpage>44</lpage>
<pub-id pub-id-type="doi">10.1002/prot.340210406</pub-id>
</element-citation>
</ref>
<ref id="CR52"><label>52</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Xiao</surname>
<given-names>X</given-names>
</name>
<name><surname>Lin</surname>
<given-names>WZ</given-names>
</name>
<name><surname>Chou</surname>
<given-names>KC</given-names>
</name>
</person-group>
<article-title>Using grey dynamic modeling and pseudo amino acid composition to predict protein structural classes</article-title>
<source>J Comp Chem</source>
<year>2008</year>
<volume>29</volume>
<fpage>2018</fpage>
<lpage>24</lpage>
<pub-id pub-id-type="doi">10.1002/jcc.20955</pub-id>
<pub-id pub-id-type="pmid">18381630</pub-id>
</element-citation>
</ref>
<ref id="CR53"><label>53</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Felsenstein</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>Phylogenies from molecular sequences: inference and reliability</article-title>
<source>Annu Rev Genet</source>
<year>1988</year>
<volume>22</volume>
<fpage>521</fpage>
<lpage>65</lpage>
<pub-id pub-id-type="doi">10.1146/annurev.ge.22.120188.002513</pub-id>
<pub-id pub-id-type="pmid">3071258</pub-id>
</element-citation>
</ref>
<ref id="CR54"><label>54</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Chatzou</surname>
<given-names>M</given-names>
</name>
<name><surname>Magis</surname>
<given-names>C</given-names>
</name>
<name><surname>Chang</surname>
<given-names>JM</given-names>
</name>
<name><surname>Kemena</surname>
<given-names>C</given-names>
</name>
<name><surname>Bussotti</surname>
<given-names>G</given-names>
</name>
<name><surname>Erb</surname>
<given-names>I</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Multiple sequence alignment modeling: methods and applications</article-title>
<source>Brief Bioinform</source>
<year>2015</year>
<volume>17</volume>
<fpage>1009</fpage>
<lpage>23</lpage>
<pub-id pub-id-type="doi">10.1093/bib/bbv099</pub-id>
<pub-id pub-id-type="pmid">26615024</pub-id>
</element-citation>
</ref>
<ref id="CR55"><label>55</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Höhl</surname>
<given-names>M</given-names>
</name>
<name><surname>Ragan</surname>
<given-names>MA</given-names>
</name>
</person-group>
<article-title>Is multiple-sequence alignment required for accurate inference of phylogeny?</article-title>
<source>Syst Biol</source>
<year>2007</year>
<volume>56</volume>
<fpage>206</fpage>
<lpage>21</lpage>
<pub-id pub-id-type="doi">10.1080/10635150701294741</pub-id>
<pub-id pub-id-type="pmid">17454975</pub-id>
</element-citation>
</ref>
<ref id="CR56"><label>56</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Wong</surname>
<given-names>KM</given-names>
</name>
<name><surname>Suchard</surname>
<given-names>MA</given-names>
</name>
<name><surname>Huelsenbeck</surname>
<given-names>JP</given-names>
</name>
</person-group>
<article-title>Alignment uncertainty and genomic analysis</article-title>
<source>Science</source>
<year>2008</year>
<volume>319</volume>
<fpage>473</fpage>
<lpage>6</lpage>
<pub-id pub-id-type="doi">10.1126/science.1151532</pub-id>
<pub-id pub-id-type="pmid">18218900</pub-id>
</element-citation>
</ref>
<ref id="CR57"><label>57</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Wu</surname>
<given-names>MT</given-names>
</name>
<name><surname>Chatterji</surname>
<given-names>S</given-names>
</name>
<name><surname>Eisen</surname>
<given-names>JA</given-names>
</name>
</person-group>
<article-title>Accounting for alignment uncertainty in phylogenomics</article-title>
<source>PLoS ONE</source>
<year>2012</year>
<volume>7</volume>
<fpage>e30288</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pone.0030288</pub-id>
<pub-id pub-id-type="pmid">22272325</pub-id>
</element-citation>
</ref>
<ref id="CR58"><label>58</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Haubold</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>Alignment-free phylogenetics and population genetics</article-title>
<source>Brief Bioinform</source>
<year>2014</year>
<volume>15</volume>
<fpage>407</fpage>
<lpage>18</lpage>
<pub-id pub-id-type="doi">10.1093/bib/bbt083</pub-id>
<pub-id pub-id-type="pmid">24291823</pub-id>
</element-citation>
</ref>
<ref id="CR59"><label>59</label>
<mixed-citation publication-type="other">Bogusz M, Whelan S. Phylogenetic Tree Estimation With and Without Alignment: New Distance Methods and Benchmarking. Syst Biol. 2016.</mixed-citation>
</ref>
<ref id="CR60"><label>60</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Sievers</surname>
<given-names>F</given-names>
</name>
<name><surname>Wilm</surname>
<given-names>A</given-names>
</name>
<name><surname>Dineen</surname>
<given-names>D</given-names>
</name>
<name><surname>Gibson</surname>
<given-names>TJ</given-names>
</name>
<name><surname>Karplus</surname>
<given-names>K</given-names>
</name>
<name><surname>Li</surname>
<given-names>W</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega</article-title>
<source>Mol Syst Biol</source>
<year>2011</year>
<volume>7</volume>
<fpage>539</fpage>
<pub-id pub-id-type="doi">10.1038/msb.2011.75</pub-id>
<pub-id pub-id-type="pmid">21988835</pub-id>
</element-citation>
</ref>
<ref id="CR61"><label>61</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Felsenstein</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>PHYLIP – Phylogeny Inference Package (Version 3.2)</article-title>
<source>Cladistics</source>
<year>1989</year>
<volume>5</volume>
<fpage>164</fpage>
<lpage>6</lpage>
</element-citation>
</ref>
<ref id="CR62"><label>62</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Jones</surname>
<given-names>DT</given-names>
</name>
<name><surname>Taylor</surname>
<given-names>WR</given-names>
</name>
<name><surname>Thornton</surname>
<given-names>JM</given-names>
</name>
</person-group>
<article-title>The rapid generation of mutation data matrices from protein sequences</article-title>
<source>CABIOS</source>
<year>1992</year>
<volume>8</volume>
<fpage>275</fpage>
<lpage>82</lpage>
<pub-id pub-id-type="pmid">1633570</pub-id>
</element-citation>
</ref>
<ref id="CR63"><label>63</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Fitch</surname>
<given-names>WM</given-names>
</name>
<name><surname>Margoliash</surname>
<given-names>E</given-names>
</name>
</person-group>
<article-title>construction of phylogenetic trees</article-title>
<source>Science</source>
<year>1967</year>
<volume>155</volume>
<fpage>279</fpage>
<lpage>84</lpage>
<pub-id pub-id-type="doi">10.1126/science.155.3760.279</pub-id>
<pub-id pub-id-type="pmid">5334057</pub-id>
</element-citation>
</ref>
<ref id="CR64"><label>64</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kuhner</surname>
<given-names>MK</given-names>
</name>
<name><surname>Felsentein</surname>
<given-names>J</given-names>
</name>
</person-group>
<article-title>A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates</article-title>
<source>Mol Biol Evol</source>
<year>1994</year>
<volume>11</volume>
<fpage>459</fpage>
<lpage>68</lpage>
<pub-id pub-id-type="pmid">8015439</pub-id>
</element-citation>
</ref>
<ref id="CR65"><label>65</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kann</surname>
<given-names>M</given-names>
</name>
<name><surname>Qian</surname>
<given-names>B</given-names>
</name>
<name><surname>Goldstein</surname>
<given-names>RA</given-names>
</name>
</person-group>
<article-title>Optimization of a new score function for the detection of remote homologs</article-title>
<source>Proteins: Struct Func Genet</source>
<year>2000</year>
<volume>41</volume>
<fpage>498</fpage>
<lpage>503</lpage>
<pub-id pub-id-type="doi">10.1002/1097-0134(20001201)41:4<498::AID-PROT70>3.0.CO;2-3</pub-id>
</element-citation>
</ref>
<ref id="CR66"><label>66</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Saigo</surname>
<given-names>H</given-names>
</name>
<name><surname>Vert</surname>
<given-names>JP</given-names>
</name>
<name><surname>Akutsu</surname>
<given-names>T</given-names>
</name>
</person-group>
<article-title>Optimizing amino acid substitution matrices with a local alignment kernel</article-title>
<source>BMC Bioinformatics</source>
<year>2006</year>
<volume>7</volume>
<fpage>246</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-7-246</pub-id>
<pub-id pub-id-type="pmid">16677385</pub-id>
</element-citation>
</ref>
</ref-list>
</back>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 0002640 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 0002640 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Pmc |étape= Corpus |type= RBID |clé= |texte= }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |