{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:24:30Z","timestamp":1760243070482,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2015,6,3]],"date-time":"2015-06-03T00:00:00Z","timestamp":1433289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>One fundamental problem of bioinformatics is the computational recognition of DNA and RNA binding sites. Given a set of short DNA or RNA sequences of equal length such as transcription factor binding sites or RNA splice sites, the task is to learn a pattern from this set that allows the recognition of similar sites in another set of DNA or RNA sequences. Permuted Markov (PM) models and permuted variable length Markov (PVLM) models are two powerful models for this task, but the problem of finding an optimal PM model or PVLM model is NP-hard. While the problem of finding an optimal PM model or PVLM model of order one is equivalent to the traveling salesman problem (TSP), the problem of finding an optimal PM model or PVLM model of order two is equivalent to the quadratic TSP (QTSP). Several exact algorithms exist for solving the QTSP, but it is unclear if these algorithms are capable of solving QTSP instances resulting from RNA splice sites of at least 150 base pairs in a reasonable time frame. Here, we investigate the performance of three exact algorithms for solving the QTSP for ten datasets of splice acceptor sites and splice donor sites of five different species and find that one of these algorithms is capable of solving QTSP instances of up to 200 base pairs with a running time of less than two days.<\/jats:p>","DOI":"10.3390\/computation3020285","type":"journal-article","created":{"date-parts":[[2015,6,3]],"date-time":"2015-06-03T11:29:39Z","timestamp":1433330979000},"page":"285-298","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem"],"prefix":"10.3390","volume":"3","author":[{"given":"Anja","family":"Fischer","sequence":"first","affiliation":[{"name":"Department of Mathematics, TU Dortmund, D-44227 Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Fischer","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, University of Kassel, D-34132 Kassel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerold","family":"J\u00e4ger","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Mathematical Statistics, University of Ume\u00e5, S-90187 Ume\u00e5, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Keilwagen","sequence":"additional","affiliation":[{"name":"Institute for Biosafety in Plant Biotechnology, Julius K\u00fchn-Institut, D-06484 Quedlinburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Molitor","sequence":"additional","affiliation":[{"name":"Institute of Computer Science and Universit\u00e4tszentrum Informatik, Martin Luther University Halle-Wittenberg, D-06120 Halle, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivo","family":"Grosse","sequence":"additional","affiliation":[{"name":"Institute of Computer Science and Universit\u00e4tszentrum Informatik, Martin Luther University Halle-Wittenberg, D-06120 Halle, Germany"},{"name":"German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, D-04103 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,6,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1093\/bioinformatics\/18.suppl_2.S100","article-title":"Identifying transcription factor binding sites through Markov chain optimization","volume":"18","author":"Ellrott","year":"2002","journal-title":"Bioinformatics"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1089\/cmb.2005.12.894","article-title":"Finding short DNA motifs using permuted Markov models","volume":"12","author":"Zhao","year":"2005","journal-title":"J. Comput. Biol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2997","DOI":"10.1093\/nar\/10.9.2997","article-title":"Use of the \u201cperceptron\u201d algorithm to distinguish translational initiation sites","volume":"10","author":"Stormo","year":"1982","journal-title":"Nucleic Acids Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1093\/nar\/12.1Part2.505","article-title":"Computer methods to locate signals in nucleic acid sequences","volume":"12","author":"Staden","year":"1984","journal-title":"Nucleic Acids Res."},{"key":"ref_5","first-page":"499","article-title":"A weight array method for splicing signal analysis","volume":"9","author":"Zhang","year":"1993","journal-title":"Comput. Appl. Biosci."},{"key":"ref_6","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Sonnenburg, S., Schweikert, G., Philips, P., Behr, J., and R\u00e4tsch, G. (2007). Accurate splice site prediction using support vector machines. BMC Bioinform., 8.","DOI":"10.1186\/1471-2105-8-S10-S7"},{"key":"ref_8","unstructured":"Yang, B., Du, D., and Wang, C.A. (2008, January 21\u201324). Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order. St. John\u2019s, NL, Canada."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.dam.2013.09.011","article-title":"Exact Algorithms and Heuristics for the Quadratic Traveling Salesman Problem with an Application in Bioinformatics","volume":"166","author":"Fischer","year":"2014","journal-title":"Discret. Appl. Math."},{"key":"ref_10","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., and Cook, W.J. (2007). The Traveling Salesman Problem: A Computational Study, Princeton University Press."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","article-title":"Dynamic Programming Treatment of the Travelling Salesman Problem","volume":"9","author":"Bellman","year":"1962","journal-title":"J. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method of solving discrete programming problems","volume":"28","author":"Land","year":"1960","journal-title":"Econometrica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian Method for the Assignment Problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_14","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01586932","article-title":"Solution of large-scale symmetric travelling salesman problems","volume":"51","author":"Holland","year":"1991","journal-title":"Math. Program. Ser. A"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","article-title":"A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems","volume":"33","author":"Padberg","year":"1991","journal-title":"SIAM Rev."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/110858665","article-title":"An Analysis of the Asymmetric Quadratic Traveling Salesman Polytope","volume":"28","author":"Fischer","year":"2014","journal-title":"SIAM J. Discret. Math."},{"key":"ref_18","unstructured":"Hong, S. (1972). A Linear Programming Approach for the Traveling Salesman Problem. [Ph.D. Thesis, John Hopkins University]."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02278710","article-title":"A shortest augmenting path algorithm for dense and sparse linear assignment problems","volume":"38","author":"Jonker","year":"1987","journal-title":"Computing"},{"key":"ref_20","unstructured":"Gurobi Optimization, Inc Available online: http:\/\/www.gurobi.com."},{"key":"ref_21","unstructured":"Available online: http:\/\/lemon.cs.elte.hu\/trac\/lemon."},{"key":"ref_22","unstructured":"Computational Biology Center http:\/\/cbio.mskcc.org\/public\/raetschlab\/user\/behr\/splicing\/."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/3\/2\/285\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:47:24Z","timestamp":1760215644000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/3\/2\/285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,3]]},"references-count":22,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2015,6]]}},"alternative-id":["computation3020285"],"URL":"https:\/\/doi.org\/10.3390\/computation3020285","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2015,6,3]]}}}