Computational Biology
@ Comenius University in Bratislava

Jakub Kováč. Gene Finding Using RT-PCR Tests. Master thesis, Comenius University in Bratislava, 2009. Supervised by Broňa Brejová.

Download preprint: 09kovacth.pdf, 843Kb

Download from publisher: http://stella.uniba.sk/zkp-storage/ddp/dostupne/FM/2009/2009-FM-QgmatO/2009-FM-QgmatO.pdf

Related web page: not available

Bibliography entry: BibTeX

Abstract:

We formulate and study a new problem in bioinformatics. This problem can be
formalized as finding the highest score s­t path in a graph. We are given 
lengths for certain pairs of vertices. If the path passes through a pair 
of vertices and the length of the subpath between these vertices has given 
length, we get bonus (otherwise we are penalized). We prove that several 
variants and subproblems are NP-hard and for some special cases we propose 
efficient algorithms.     

The problem is (weakly) NP-hard even for a single pair, but can be solved
in pseudopolynomial time; we also propose an approximative solution. Then 
we study a problem of finding an s­t path that avoids all the \\"forbidden\\" 
pairs of vertices or finding a path that collects \\"useful\\" pairs of 
vertices. These are the special cases of our problem (if we forget about 
scores and lengths) and turn out to be the hard core of our problem. 
Complexity of these problems depends to a large extent to the mutual 
positions of the pairs. We introduce 7 natural classes of sets of pairs 
for which we try to solve the problems. We prove the problem (strongly) 
NP-hard for some classes and we propose efficient algorithms for other 
classes (thus we study the borderline between the NP-hardness and 
efficient solvability).