{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T07:31:03Z","timestamp":1761291063004,"version":"3.37.3"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2018,4,19]],"date-time":"2018-04-19T00:00:00Z","timestamp":1524096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Innovation by Science and Technology in Flanders"},{"DOI":"10.13039\/501100003130","name":"Research Foundation Flanders","doi-asserted-by":"publisher","award":["G.0328.16N"],"award-info":[{"award-number":["G.0328.16N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Evolutionary information is crucial for the annotation of proteins in bioinformatics. The amount of retrieved homologs often correlates with the quality of predicted protein annotations related to structure or function. With a growing amount of sequences available, fast and reliable methods for homology detection are essential, as they have a direct impact on predicted protein annotations.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We developed a discriminative, alignment-free algorithm for homology detection with quasi-linear complexity, enabling theoretically much faster homology searches. To reach this goal, we convert the protein sequence into numeric biophysical representations. These are shrunk to a fixed length using a novel vector quantization method which uses a Discrete Cosine Transform compression. We then compute, for each compressed representation, similarity scores between proteins with the Dynamic Time Warping algorithm and we feed them into a Random Forest. The WARP performances are comparable with state of the art methods.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The method is available at http:\/\/ibsquare.be\/warp.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty309","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T20:54:04Z","timestamp":1524084844000},"page":"3118-3125","source":"Crossref","is-referenced-by-count":15,"title":["Ultra-fast global homology detection with Discrete Cosine Transform and Dynamic Time Warping"],"prefix":"10.1093","volume":"34","author":[{"given":"Daniele","family":"Raimondi","sequence":"first","affiliation":[{"name":"Interuniversity Institute of Bioinformatics in Brussels, ULB-VUB, Brussels, Belgium"},{"name":"Structural Biology Brussels, Vrije Universiteit Brussel, Brussels, Belgium"},{"name":"ESAT-STADIUS, KU Leuven, Leuven, Belgium"},{"name":"Machine Learning Group, Universit\u00e9 Libre De Bruxelles, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriele","family":"Orlando","sequence":"additional","affiliation":[{"name":"Interuniversity Institute of Bioinformatics in Brussels, ULB-VUB, Brussels, Belgium"},{"name":"Structural Biology Brussels, Vrije Universiteit Brussel, Brussels, Belgium"},{"name":"Machine Learning Group, Universit\u00e9 Libre De Bruxelles, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yves","family":"Moreau","sequence":"additional","affiliation":[{"name":"ESAT-STADIUS, KU Leuven, Leuven, Belgium"},{"name":"Imec, Leuven, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7470-4324","authenticated-orcid":false,"given":"Wim F","family":"Vranken","sequence":"additional","affiliation":[{"name":"Interuniversity Institute of Bioinformatics in Brussels, ULB-VUB, Brussels, Belgium"},{"name":"Structural Biology Brussels, Vrije Universiteit Brussel, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,4,19]]},"reference":[{"key":"2023012704180872100_bty309-B1","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/T-C.1974.223784","article-title":"Discrete cosine transform","volume":"C-23","author":"Ahmed","year":"1974","journal-title":"IEEE Trans. Computers"},{"key":"2023012704180872100_bty309-B3","doi-asserted-by":"crossref","first-page":"i26","DOI":"10.1093\/bioinformatics\/btg1002","article-title":"Remote homology detection: a motif based approach","volume":"19","author":"Ben-Hur","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B4","doi-asserted-by":"crossref","first-page":"3770","DOI":"10.1073\/pnas.0810767106","article-title":"Sequence context-specific profiles for homology searching","volume":"106","author":"Biegert","year":"2009","journal-title":"PNAS"},{"key":"2023012704180872100_bty309-B5","doi-asserted-by":"crossref","first-page":"W29","DOI":"10.1093\/nar\/gkt282","article-title":"BLAST: a more efficient report with usability improvements","volume":"41","author":"Boratyn","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023012704180872100_bty309-B6","first-page":"532","article-title":"Random forests","volume":"45","author":"Breiman","year":"2001","journal-title":"Mach. Learn"},{"key":"2023012704180872100_bty309-B7","doi-asserted-by":"crossref","first-page":"2684","DOI":"10.1093\/bioinformatics\/btx217","article-title":"EigenTHREADER: analogous protein fold recognition by efficient contact map threading","volume":"33","author":"Buchan","year":"2017","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/ncomms3741","article-title":"From protein sequence to dynamics and disorder with DynaMine","volume":"4","author":"Cilia","year":"2013","journal-title":"Nat. Commun"},{"key":"2023012704180872100_bty309-B9","first-page":"316","article-title":"Vector quantization kernels for the classification of protein sequences and structures","volume":"2014","author":"Clark","year":"2013","journal-title":"Biocomputing"},{"year":"2005","author":"Dong","key":"2023012704180872100_bty309-B10"},{"key":"2023012704180872100_bty309-B11","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1038\/nature02579","article-title":"Genome evolution in yeasts","volume":"430","author":"Dujon","year":"2004","journal-title":"Nature"},{"key":"2023012704180872100_bty309-B12","doi-asserted-by":"crossref","first-page":"e1002195.","DOI":"10.1371\/journal.pcbi.1002195","article-title":"Accelerated profile HMMsearches","volume":"7","author":"Eddy","year":"2011","journal-title":"PLoS Comput. Biol"},{"key":"2023012704180872100_bty309-B13","first-page":"2460","article-title":"Search and clustering orders of magnitude faster than BLAST","volume":"26","author":"Edgar","year":"2010","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012704180872100_bty309-B14","doi-asserted-by":"crossref","first-page":"W29","DOI":"10.1093\/nar\/gkr367","article-title":"HMMER web server: interactive sequence similarity searching","volume":"39","author":"Finn","year":"2011","journal-title":"Nucleic Acids Res"},{"key":"2023012704180872100_bty309-B15","doi-asserted-by":"crossref","first-page":"D222","DOI":"10.1093\/nar\/gkt1223","article-title":"Pfam: the protein families database","volume":"42","author":"Finn","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023012704180872100_bty309-B17","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1093\/bioinformatics\/btr638","article-title":"PSICOV: precise structural contact prediction using sparse inverse covariance estimation on large multiple sequence alignments","volume":"28","author":"Jones","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B18","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1038\/nature01256","article-title":"The structure of the protein universe and genome evolution","volume":"420","author":"Koonin","year":"2002","journal-title":"Nature"},{"key":"2023012704180872100_bty309-B19","doi-asserted-by":"crossref","first-page":"D240","DOI":"10.1093\/nar\/gkt1205","article-title":"Gene3D: multi-domain annotations for protein sequence and comparative genome analysis","volume":"42","author":"Lees","year":"2014","journal-title":"Nucleic Acids Res"},{"year":"2002","author":"Leslie","key":"2023012704180872100_bty309-B20"},{"key":"2023012704180872100_bty309-B21","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1093\/bioinformatics\/btg431","article-title":"Mismatch string kernels for discriminative protein classification","volume":"20","author":"Leslie","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B22","doi-asserted-by":"crossref","first-page":"1919","DOI":"10.1007\/s00438-015-1044-4","article-title":"Protein remote homology detection by combining Chous distance-pair pseudo amino acid composition and principal component analysis","volume":"290","author":"Liu","year":"2015","journal-title":"Mol. Genet. Genomics"},{"key":"2023012704180872100_bty309-B23","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1093\/bioinformatics\/btt709","article-title":"Combining evolutionary information extracted from frequency profiles with sequence-based kernels for protein remote homology detection","volume":"30","author":"Liu","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/TASSP.1980.1163351","article-title":"A fast cosine transform in one and two dimensions","volume":"28","author":"Makhoul","year":"1980","journal-title":"IEEE Trans. Acoustics Speech Signal Process"},{"key":"2023012704180872100_bty309-B25","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1093\/bioinformatics\/16.4.404","article-title":"The PSIPRED protein structure prediction server","volume":"16","author":"McGuffin","year":"2000","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B26","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol"},{"key":"2023012704180872100_bty309-B27","doi-asserted-by":"crossref","first-page":"D227","DOI":"10.1093\/nar\/gku1041","article-title":"The SUPERFAMILY 1.75 database in 2014: a doubling of data","volume":"43","author":"Oates","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023012704180872100_bty309-B28","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/MCSE.2007.58","article-title":"Python for scientific computing","volume":"9","author":"Oliphant","year":"2007","journal-title":"Comput. Sci. Eng"},{"key":"2023012704180872100_bty309-B29","doi-asserted-by":"crossref","first-page":"36679.","DOI":"10.1038\/srep36679","article-title":"Observation selection bias in contact prediction and its implications for structural bioinformatics","volume":"6","author":"Orlando","year":"2016","journal-title":"Sci. Rep"},{"key":"2023012704180872100_bty309-B30","first-page":"1","article-title":"SVM-dependent pairwise HMM: an application to protein pairwise alignments","volume":"2017","author":"Orlando","year":"2017","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B31","doi-asserted-by":"crossref","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","article-title":"Improved tools for biological sequence comparison","volume":"85","author":"Pearson","year":"1988","journal-title":"PNAS"},{"key":"2023012704180872100_bty309-B32","first-page":"2825","article-title":"Scikit-learn: machine learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"JMLR"},{"key":"2023012704180872100_bty309-B33","first-page":"1","article-title":"Clustering-based model of cysteine co-evolution improves disulfide bond connectivity prediction and reduces homologous sequence requirements","volume":"2014","author":"Raimondi","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B34","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1038\/nmeth.1818","article-title":"HHblits: lightning-fast iterative protein sequence searching byHMM-HMM alignment","volume":"9","author":"Remmert","year":"2012","journal-title":"Nat. Methods"},{"key":"2023012704180872100_bty309-B35","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1093\/bioinformatics\/btw094","article-title":"Multilevel biological characterization of exomic variants at the protein level significantly improves the identification of their deleterious effects","volume":"32","author":"Raimondi","year":"2016","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B36","doi-asserted-by":"crossref","DOI":"10.1038\/s41598-017-08366-3","article-title":"Exploring the sequence-based prediction of folding initiation sites in proteins","volume":"7","author":"Raimondi","year":"2017","journal-title":"Sci. Rep"},{"key":"2023012704180872100_bty309-B37","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1002\/humu.23129","article-title":"Investigating the molecular mechanisms behind uncharacterized cysteine losses from prediction of their oxidation state","volume":"38","author":"Raimondi","year":"2017","journal-title":"Hum. Mutat"},{"key":"2023012704180872100_bty309-B38","doi-asserted-by":"crossref","first-page":"221.","DOI":"10.1186\/1471-2105-12-221","article-title":"Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation","volume":"12","author":"Rognes","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023012704180872100_bty309-B39","doi-asserted-by":"crossref","first-page":"1682","DOI":"10.1093\/bioinformatics\/bth141","article-title":"Protein homology detection using string alignment kernels","volume":"20","author":"Saigo","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B40","doi-asserted-by":"crossref","first-page":"561","DOI":"10.3233\/IDA-2007-11508","article-title":"FastDTW: toward accurate dynamic time warping in linear time and space","volume":"11.5","author":"Salvador","year":"2007","journal-title":"Intelligent Data Analysis"},{"key":"2023012704180872100_bty309-B41","doi-asserted-by":"crossref","first-page":"2636","DOI":"10.1093\/bioinformatics\/btw305","article-title":"Benchmarking the next generation of homology inference tools","volume":"32","author":"Saripella","year":"2016","journal-title":"Bioinformatics"},{"key":"2023012704180872100_bty309-B42","doi-asserted-by":"crossref","first-page":"e1003889.","DOI":"10.1371\/journal.pcbi.1003889","article-title":"Improved contact predictions using the recognition of protein like contact patterns","volume":"10","author":"Skwark","year":"2014","journal-title":"PLoS Comput. Biol"},{"key":"2023012704180872100_bty309-B43","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol"},{"key":"2023012704180872100_bty309-B44","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1093\/bioinformatics\/bti125","article-title":"Protein homology detection by HMM-HMM Comparison","volume":"21","author":"Soding","year":"2005","journal-title":"Bioinformatics (Oxford, England)"},{"key":"2023012704180872100_bty309-B45","doi-asserted-by":"crossref","first-page":"D142","DOI":"10.1093\/nar\/gkp846","article-title":"The universal protein resource (UniProt) in 2010","volume":"38","author":"UniProt Consortium","year":"2010","journal-title":"Nucleic Acids Res"},{"volume-title":"Statistical Learning Theory","year":"1998","author":"Vapnik","key":"2023012704180872100_bty309-B46"},{"key":"2023012704180872100_bty309-B47","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s11263-006-9794-4","article-title":"Local features and kernels for classification of texture and object categories: a comprehensive study","volume":"73","author":"Zhang","year":"2007","journal-title":"Int. J. Computer Vision"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/18\/3118\/48919380\/bioinformatics_34_18_3118.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/18\/3118\/48919380\/bioinformatics_34_18_3118.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T04:40:05Z","timestamp":1674794405000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/18\/3118\/4978051"}},"subtitle":[],"editor":[{"given":"John","family":"Hancock","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,4,19]]},"references-count":45,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2018,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty309","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2018,9,15]]},"published":{"date-parts":[[2018,4,19]]}}}