Full metadata record
DC FieldValueLanguage
dc.contributor.authorFischer, Anja-
dc.contributor.authorFischer, Frank-
dc.contributor.authorJäger, Gerold-
dc.contributor.authorKeilwagen, Jens-
dc.contributor.authorMolitor, Paul-
dc.contributor.authorGrosse, Ivo-
dc.date.accessioned2019-10-14T13:15:27Z-
dc.date.available2019-10-14T13:15:27Z-
dc.date.issued2015-06-03-
dc.identifier.urihttp://hdl.handle.net/2003/38280-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-20250-
dc.description.abstractOne 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.en
dc.language.isoende
dc.relation.ispartofseriesComputation;3(2)-
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/-
dc.subjectSplice siteen
dc.subjectPermuted Markov modelen
dc.subjectPermuted variable length Markov modelen
dc.subjectQuadratic traveling salesman problemen
dc.subjectCombinatorial optimizationen
dc.subjectDynamic programmingen
dc.subjectBranch and bounden
dc.subjectBranch and cuten
dc.subjectInteger linear programmingen
dc.subject.ddc510-
dc.titleComputational recognition of RNA splice sites by exact algorithms for the quadratic traveling salesman problemen
dc.typeTextde
dc.type.publicationtypearticlede
dc.subject.rswkRNA-Spleißende
dc.subject.rswkMarkov-Modellde
dc.subject.rswkTravelling-salesman-Problemde
dcterms.accessRightsopen access-
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primaryidentifierdoi:10.3390/computation3020285de
eldorado.secondarypublication.primarycitationFischer, A.; Fischer, F.; Jäger, G.; Keilwagen, J.; Molitor, P.; Grosse, I. Computational Recognition of RNA Splice Sites by Exact Algorithms for the Quadratic Traveling Salesman Problem. Computation 2015, 3, 285-298.de
Appears in Collections:Lehrstuhl V Diskrete Optimierung

Files in This Item:
File Description SizeFormat 
computation-03-00285-v2.pdf249.26 kBAdobe PDFView/Open


This item is protected by original copyright



This item is licensed under a Creative Commons License Creative Commons