Tuning DNA fragment assembly algorithms
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Diplomityö
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2008
Department
Major/Subject
Ohjelmistotekniikka
Mcode
T-106
Degree programme
Language
en
Pages
(8) + 55 s. + liitt. 2
Series
Abstract
DNA-osien yhdistely on keskeinen osa tämän päivän DNA-sekvenointiprojekteja. Nykyiset sekvenointiteknologiat mahdollistavat vain lyhyiden DNA-pätkien sekvenoinnin kerrallaan, joten alkuperäinen genomi täytyy rekonstruoida näistä pienemmistä pätkistä. Tämän ongelman ratkaisemiseksi toteutetaan tässä työssä uusi yhdistelyalgoritmi nimeltä PMSGA. Tämä algoritmi perustuu päällekkäisyys-järjestys-konsensus paradigmaan. Päällekkäisyysvaihe perustuu ideaan yhteisten hahmojen esiintymien käyttämiseen frakmenttien päällekkäisyyksien määrittämiseen, järjestysvaihe perustuu ideaan pienimmän kustannuksen verkkovirtauksen käyttämisestä päällekkäisyysgraafin kaarien vierailujen lukumäärään määrittämiseen ja konsensusvaihe perustuu omaan ideaan käyttää paikkariippuvaista q-grammien hajautusta loppusekvenssin määrittämiseen. PMSGA:ta verrattiin joukkoon yleisesti käytettyjä DNA-palasten yhdistelyalgoritmeja. Tämä algoritmi on nopeampi kuin mikään muista verrattavista algoritmeista. Algoritmien tulosteita myös vertailtiin keskenään. PMSGA tuotti vähemmän yhdistelyvirheitä kuin muut algoritmit, mutta lopputuloksen peite suhteessa kohdesekvenssiin oli pienempi. Tässä toteutuksessa toistoksi määritetyt alijonot poistetaan lopputuloksesta virheiden välttämiseksi.Description
Supervisor
Tarhio, JormaThesis advisor
Tarhio, JormaKeywords
fragment assembly, DNA-palasten yhdistely, DNA sequencing, DNA-sekventointi, pattern matching, hahmonhaku, string graph, merkkijonograafit, sequence reconstruction, sekvenssin rekonstruktio