Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Show others and affiliations
2015 (English)In: Computation, E-ISSN 2079-3197, Vol. 3, no 2, 285-298 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2015. Vol. 3, no 2, 285-298 p.
Keyword [en]
splice site, permuted Markov model, permuted variable length Markov model, quadratic traveling salesman problem, combinatorial optimization, dynamic programming, branch and bound, branch and cut, integer linear programming
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:umu:diva-103009DOI: 10.3390/computation3020285ISI: 000362074700005OAI: oai:DiVA.org:umu-103009DiVA: diva2:812010
Available from: 2015-05-14 Created: 2015-05-14 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

fulltext(619 kB)67 downloads
File information
File name FULLTEXT01.pdfFile size 619 kBChecksum SHA-512
9e3cf364f9498843f1d0e7e9e55d6a719799b843ab4f9e52530f1a0845813a8500c7905117c12ca46cebf08ab39a2251ba22c4754a11e52e9bcc08ba6cebfb71
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Computation
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 67 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 115 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf