Modele grafowe i algorytmy dla klasycznego problemu sekwencjonowania DNA przez hybrydyzacje oraz dla jego odmiany z informacja o powtórzeniach
[ 1 ] Wydział Informatyki, Politechnika Poznańska | [ D ] phd student
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
EN Graph models and algorithms for classical DNA sequencing by hybridization and for the variant of the problem with information about repetitions
polish
- sekwencjonowanie przez hybrydyzację
- orienteering
- algorytm aproksymacyjny
- przeszukiwanie tabu
- algorytm kolonii mrówek
- sequencing by hybridization
- orienteering
- approximation algorithm
- tabu search
- ant colony optimization
PL Jednym z podstawowych problemów dotyczących sekwencjonowania DNA przez hybrydyzację (SBH) są błędy pojawiające się w trakcie eksperymentu biochemicznego. Są one powodowane m.in. przez powtórzenia oligonukleotydów wchodzących w skład analizowanej sekwencji. Obecnie nie ma technologicznych możliwości ustalenia dokładnej liczby powtórzeń poszczególnych oligonukleotydów, dlatego rozważane są modele częściowej informacji o powtórzeniach. Przedstawiono dla nich następujące algorytmy: zachłanny, przeszukiwania tabu oraz dwa algorytmy kolonii mrówek. Wyniki eksperymentów wykazały, że zastosowanie nawet częściowej informacji o powtórzeniach prowadzi do lepszej rekonstrukcji sekwencji. W pracy zaproponowano również algorytm aproksymacyjny dla klasycznego problemu SBH, który odpowiada grafowemu problemowi Orienteering. Wykazano, że dla problemu Orienteering w grafie skierowanym istnieje algorytm aproksymacyjny o stałym współczynniku aproksymacji, o ile iloraz największego do najmniejszego kosztu łuku w danym grafie jest ograniczony pewną stałą.
EN Errors occurring during the biochemical experiment are one of the most important issues related to DNA sequencing by hybridization (SBH). They are caused, for example, by repetitions in an analyzed sequence. The current technology does not enable to determine the exact number of repetitions for oligonucleotides the sequence consist of. Thus, models assuming a partial information about repetition are taken into account. They have been used to propose the following algorithms: greedy, tabu search and two ant colony optimization algorithms. The obtained results confirmed that even partial information about repetitions improves sequence reconstruction. The classical SBH problem corresponds to a graph problem called Orienteering. An approximation algorithm for Orienteering in directed graph has been proposed too. It has been shown that if the ratio between the maximum and the minimum arc cost in an input graph is bounded by a constant factor then the proposed algorithm has a constant factor performance guarantee.
110
computer sciences and computer science
computer science
DrOIN 1573
public
Sebastian Deorowicz
Gliwice, Polska
04.07.2013
polish
public
Marta Kasprzak
Poznań, Polska
24.06.2013
polish
public
Wojciech T. Markiewicz
Poznań, Polska
24.06.2013
polish
public
dissertation
Poznań, Polska
07.02.2014
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności: bioinformatyka