{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T14:54:59Z","timestamp":1780325699002,"version":"3.54.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2016,12,5]],"date-time":"2016-12-05T00:00:00Z","timestamp":1480896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"name":"SYSCOL","award":["258236"],"award-info":[{"award-number":["258236"]}]},{"name":"Academy of Finland CoE in Cancer Genetics Research","award":["250345"],"award-info":[{"award-number":["250345"]}]},{"name":"NIASC","award":["62721"],"award-info":[{"award-number":["62721"]}]},{"name":"Icelandic Research Fund","award":["152679-051"],"award-info":[{"award-number":["152679-051"]}]},{"name":"Icelandic Research Fund","award":["VP12014044"],"award-info":[{"award-number":["VP12014044"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>While the position weight matrix (PWM) is the most popular model for sequence motifs, there is growing evidence of the usefulness of more advanced models such as first-order Markov representations, and such models are also becoming available in well-known motif databases. There has been lots of research of how to learn these models from training data but the problem of predicting putative sites of the learned motifs by matching the model against new sequences has been given less attention. Moreover, motif site analysis is often concerned about how different variants in the sequence affect the sites. So far, though, the corresponding efficient software tools for motif matching have been lacking.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We develop fast motif matching algorithms for the aforementioned tasks. First, we formalize a framework based on high-order position weight matrices for generic representation of motif models with dinucleotide or general q-mer dependencies, and adapt fast PWM matching algorithms to the high-order PWM framework. Second, we show how to incorporate different types of sequence variants, such as SNPs and indels, and their combined effects into efficient PWM matching workflows. Benchmark results show that our algorithms perform well in practice on genome-sized sequence sets and are for multiple motif search much faster than the basic sliding window algorithm.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and Implementation<\/jats:title>\n                  <jats:p>Implementations are available as a part of the MOODS software package under the GNU General Public License v3.0 and the Biopython license (http:\/\/www.cs.helsinki.fi\/group\/pssmfind).<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btw683","type":"journal-article","created":{"date-parts":[[2016,10,27]],"date-time":"2016-10-27T19:06:40Z","timestamp":1477595200000},"page":"514-521","source":"Crossref","is-referenced-by-count":44,"title":["Fast motif matching revisited: high-order PWMs, SNPs and indels"],"prefix":"10.1093","volume":"33","author":[{"given":"Janne H","family":"Korhonen","sequence":"first","affiliation":[{"name":"School of Computer Science, Reykjav\u00edk University, Reykjav\u00edk, Iceland"},{"name":"Helsinki Institute for Information Technology HIIT, Helsinki, Finland"},{"name":"Department of Computer Science, Faculty of Medicine, University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kimmo","family":"Palin","sequence":"additional","affiliation":[{"name":"Genome-Scale Biology Research Program, Research Programs Unit, Faculty of Medicine, University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jussi","family":"Taipale","sequence":"additional","affiliation":[{"name":"Department of Biosciences and Nutrition, Karolinska Institutet, Genome Scale Biology Program, Faculty of Medicine, University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esko","family":"Ukkonen","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Helsinki, Finland"},{"name":"Department of Computer Science, Faculty of Medicine, University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2016,12,5]]},"reference":[{"key":"2023020204412761400_btw683-B1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","article-title":"Efficient string matching: an aid to bibliographic search","volume":"18","author":"Aho","year":"1975","journal-title":"Commun. ACM"},{"key":"2023020204412761400_btw683-B2","doi-asserted-by":"crossref","first-page":"12.","DOI":"10.1371\/journal.pcbi.0040005","article-title":"In silico detection of sequence variations modifying transcriptional regulation","volume":"4","author":"Andersen","year":"2008","journal-title":"PLoS Comput. Biol"},{"key":"2023020204412761400_btw683-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1371\/journal.pone.0020059","article-title":"A linear model for transcription factor binding affinity prediction in protein binding microarrays","volume":"6","author":"Annala","year":"2011","journal-title":"PLoS ONE"},{"key":"2023020204412761400_btw683-B4","author":"Beckstette","year":"2004"},{"key":"2023020204412761400_btw683-B5","doi-asserted-by":"crossref","first-page":"1429","DOI":"10.1038\/nbt1246","article-title":"Compact, universal DNA microarrays to comprehensively determine transcription-factor binding site specificities","volume":"24","author":"Berger","year":"2006","journal-title":"Nat. Biotechnol"},{"key":"2023020204412761400_btw683-B6","author":"Dorohonceanu","year":"2000"},{"key":"2023020204412761400_btw683-B7","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1089\/cmb.2012.0289","article-title":"Fast matching of transcription factor motifs using generalized position weight matrix models","volume":"20","author":"Giaquinta","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2023020204412761400_btw683-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.06.032","article-title":"Motif matching using gapped patterns","volume":"548","author":"Giaquinta","year":"2014","journal-title":"Theor. Comput. Sci"},{"key":"2023020204412761400_btw683-B9","doi-asserted-by":"crossref","first-page":"4355","DOI":"10.1073\/pnas.84.13.4355","article-title":"Profile analysis: detection of distantly related proteins","volume":"84","author":"Gribskov","year":"1987","journal-title":"Proc. Natl. Acad. Sci. U. S. A"},{"key":"2023020204412761400_btw683-B10","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0076-6879(90)83009-X","article-title":"Finding protein similarities with nucleotide sequence databases","volume":"183","author":"Henikoff","year":"1990","journal-title":"Methods Enzymol"},{"key":"2023020204412761400_btw683-B11","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.cell.2012.12.009","article-title":"DNA-binding specificities of human transcription factors","volume":"152","author":"Jolma","year":"2013","journal-title":"Cell"},{"key":"2023020204412761400_btw683-B12","doi-asserted-by":"crossref","first-page":"3181","DOI":"10.1093\/bioinformatics\/btp554","article-title":"MOODS: fast search for position weight matrix matches in DNA sequences","volume":"25","author":"Korhonen","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020204412761400_btw683-B13","doi-asserted-by":"crossref","DOI":"10.1142\/S0219720013400040","article-title":"From binding motifs in ChIP-Seq data to improved models of transcription factor binding sites","volume":"11","author":"Kulakovskiy","year":"2013","journal-title":"J. Bioinf. Comput. Biol"},{"key":"2023020204412761400_btw683-B14","doi-asserted-by":"crossref","first-page":"D116","DOI":"10.1093\/nar\/gkv1249","article-title":"HOCOMOCO: expansion and enhancement of the collection of transcription factor binding sites models","volume":"44","author":"Kulakovskiy","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020204412761400_btw683-B15","author":"Liefooghe","year":"2009"},{"key":"2023020204412761400_btw683-B16","doi-asserted-by":"crossref","first-page":"i524","DOI":"10.1093\/bioinformatics\/btq378","article-title":"is-rSNP: a novel technique for in silico regulatory SNP detection","volume":"26","author":"Macintyre","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020204412761400_btw683-B17","doi-asserted-by":"crossref","first-page":"2471","DOI":"10.1093\/nar\/29.12.2471","article-title":"Non-independence of mnt repressor\u2013operator interaction determined by a new quantitative multiple fluorescence relative affinity (QuMFRA) assay","volume":"29","author":"Man","year":"2001","journal-title":"Nucleic Acids Res"},{"key":"2023020204412761400_btw683-B18","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pcbi.1003214","article-title":"The next generation of transcription factor binding site prediction","volume":"9","author":"Mathelier","year":"2013","journal-title":"PLoS Comput. Biol"},{"key":"2023020204412761400_btw683-B19","doi-asserted-by":"crossref","first-page":"D116","DOI":"10.1093\/nar\/gkv1176","article-title":"Jaspar 2016: a major expansion and update of the open-access database of transcription factor binding profiles","volume":"44","author":"Mathelier","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020204412761400_btw683-B20","doi-asserted-by":"crossref","first-page":"i117","DOI":"10.1093\/bioinformatics\/btt221","article-title":"Stability selection for regression-based models of transcription factor\u2013DNA binding specificity","volume":"29","author":"Mordelet","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020204412761400_btw683-B21","doi-asserted-by":"crossref","DOI":"10.1038\/ncomms10050","article-title":"Structural insights into the DNA-binding specificity of E2F family transcription factors","volume":"6","author":"Morgunova","year":"2015","journal-title":"Nat. Commun"},{"key":"2023020204412761400_btw683-B22","doi-asserted-by":"crossref","DOI":"10.7554\/eLife.04837","article-title":"Conservation of transcription factor binding specificities across 600 million years of bilateria evolution","volume":"4","author":"Nitta","year":"2015","journal-title":"eLife"},{"key":"2023020204412761400_btw683-B23","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.tcs.2008.01.015","article-title":"Fast profile matching algorithms \u2013 a survey","volume":"395","author":"Pizzi","year":"2008","journal-title":"Theor. Comput. Sci"},{"key":"2023020204412761400_btw683-B24","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/TCBB.2009.35","article-title":"Finding significant matches of position weight matrices in linear time","volume":"8","author":"Pizzi","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023020204412761400_btw683-B25","doi-asserted-by":"crossref","first-page":"S7","DOI":"10.1186\/1471-2164-13-S4-S7","article-title":"Large-scale computational identification of regulatory SNPs with rSNP-MAPPER","volume":"13","author":"Riva","year":"2012","journal-title":"BMC Genomics"},{"key":"2023020204412761400_btw683-B26","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/978-3-540-75530-2_25","volume-title":"14th International Symposium on String Processing and Information Retrieval (SPIRE 2007)","author":"Salmela","year":"2007"},{"key":"2023020204412761400_btw683-B27","doi-asserted-by":"crossref","first-page":"e99015","DOI":"10.1371\/journal.pone.0099015","article-title":"A general pairwise interaction model provides an accurate description of in vivo transcription factor binding sites","volume":"9","author":"Santolini","year":"2014","journal-title":"PLoS ONE"},{"key":"2023020204412761400_btw683-B28","doi-asserted-by":"crossref","first-page":"e1000154","DOI":"10.1371\/journal.pcbi.1000154","article-title":"A feature-based approach to modeling protein-DNA interactions","volume":"4","author":"Sharon","year":"2008","journal-title":"PLoS Comput. Biol"},{"key":"2023020204412761400_btw683-B29","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pone.0009722","article-title":"Dinucleotide weight matrices for predicting transcription factor binding sites: Generalizing the position weight matrix","volume":"5","author":"Siddharthan","year":"2010","journal-title":"PLoS ONE"},{"key":"2023020204412761400_btw683-B30","first-page":"gkw521.","article-title":"Bayesian markov models consistently outperform PWMs at predicting motifs in nucleotide sequences","author":"Siebert","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020204412761400_btw683-B31","first-page":"89","article-title":"Methods for calculating the probabilities of finding patterns in sequences","volume":"5","author":"Staden","year":"1989","journal-title":"Comput. Appl. Biosci. (CABIOS)"},{"key":"2023020204412761400_btw683-B32","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1093\/bioinformatics\/16.1.16","article-title":"DNA binding sites: representation and discovery","volume":"16","author":"Stormo","year":"2000","journal-title":"Bioinformatics"},{"key":"2023020204412761400_btw683-B33","doi-asserted-by":"crossref","first-page":"2997","DOI":"10.1093\/nar\/10.9.2997","article-title":"Use of the \u2018perceptron\u2019 algorithm to distinguish translational initiation sites in E. coli","volume":"10","author":"Stormo","year":"1982","journal-title":"Nucleic Acids Res"},{"key":"2023020204412761400_btw683-B34","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","author":"The 1000 Genomes Project Consortium","year":"2015","journal-title":"Nature"},{"key":"2023020204412761400_btw683-B35","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1038\/35057062","article-title":"Initial sequencing and analysis of the human genome","volume":"409","author":"The Genome Sequencing Consortium","year":"2001","journal-title":"Nature"},{"key":"2023020204412761400_btw683-B36","first-page":"1754","article-title":"Transcription factor binding predictions using TRAP for the analysis of ChIP-seq data and regulatory SNPs","volume":"6","author":"Thomas-Chollier","year":"2011","journal-title":"BMC Genomics"},{"key":"2023020204412761400_btw683-B37","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1038\/ng.406","article-title":"The common colorectal cancer predisposition SNP rs6983267 at chromosome 8q24 confers potential to enhanced Wnt signaling","volume":"41","author":"Tuupanen","year":"2009","journal-title":"Nat. Genet"},{"key":"2023020204412761400_btw683-B38","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1038\/nbt.2486","article-title":"Evaluation of methods for modeling transcription factor sequence specificity","volume":"31","author":"Weirauch","year":"2013","journal-title":"Nat. Biotechnol"},{"key":"2023020204412761400_btw683-B39","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1093\/bioinformatics\/16.3.233","article-title":"Fast probabilistic analysis of sequence function using scoring matrices","volume":"16","author":"Wu","year":"2000","journal-title":"Bioinformatics"},{"key":"2023020204412761400_btw683-B40","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1534\/genetics.112.138685","article-title":"Improved models for transcription factor binding site identification using nonindependent interactions","volume":"191","author":"Zhao","year":"2012","journal-title":"Genetics"},{"key":"2023020204412761400_btw683-B41","doi-asserted-by":"crossref","first-page":"3353","DOI":"10.1093\/bioinformatics\/btv328","article-title":"atSNP: transcription factor binding affinity testing for regulatory SNP detection","volume":"31","author":"Zuo","year":"2015","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/4\/514\/49037769\/bioinformatics_33_4_514.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/4\/514\/49037769\/bioinformatics_33_4_514.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T04:45:53Z","timestamp":1675313153000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/4\/514\/2726114"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2016,12,5]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw683","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,2,15]]},"published":{"date-parts":[[2016,12,5]]}}}