Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.:Mathematics and biology - having nothing in common?
I. Going for a start
1. Introducing haplotyping
2. Becoming mathematical
II. The MRS problem
3. The graph theoretical point of view
3.1. The MRS problem
3.2. The MRS problem on special graph classes
4. Trying to be not that bad
4.1. Greedy approaches
4.2. The local colour density
4.3. MaxNewColour
5. What is real data telling us?
And the work goes on and on
Bibliography
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:22803 |
| Date | 13 March 2012 |
| Creators | Matos Camacho, Stephan |
| Contributors | Schiermeyer, Ingo, Randerath, Hubert, TU Bergakademie Freiberg |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds