We present a set of results concerning two types of biological problems: (1) RNA structure comparison and (2) intergenomic distance computation con- sidering non trivial genomes. In this thesis, we determine the algorithmic complexity of a set of problems linked to either RNA structure comparison (edit distance, APS problem, 2-interval pattern extraction, RNA design), or genomic rearrangements (breakpoints and conserved intervals distances). For each studied problem, we try to find an exact and fast algorithm resolving it. If we do not find such an algorithm, we try to prove that it is impossible to find one. To do so, we prove that the corresponding problem is difficult. Finally, we continue the study of each difficult problem by proposing three types of results: (1) Approximation, (2) Parameterized complexity, (3) Heuris- tic. We use in this thesis notions of combinatorics, mathematics, graph theory and algorithmics.
from HAL : Dernières publications http://ift.tt/1tUYamd
from HAL : Dernières publications http://ift.tt/1tUYamd
0 commentaires:
Enregistrer un commentaire