@ 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 st 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 st 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).