GRASShopPER – wydajna metoda asemblacji de novo wykorzystująca strategię Overlap-Layout-Consensus
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
EN GRASShopPER – the new efficient approach to de novo genome assembly using Overlap-Layout-Consensus strategy
polish
- asemblacja
- sekwencjonowanie
- bioinformatyka
- heurystyka
- assembly
- sequencing
- bioinformatics
- heuristic
PL Asemblacja DNA stanowi jeden z kluczowych elementów złożonego procesu sekwencjonowania materiału genetycznego. Istotą procesu asemblacji jest rekonstrukcja możliwie długiej sekwencji nukleotydów materiału genetycznego przy wykorzystaniu jego krótkich lecz silnie, przy tym nierównomiernie, nakładających się fragmentów. Fragmenty podlegające takiej rekonstrukcji, określane mianem odczytów, z powodu ograniczeń technologicznych nie mogą być wydłużone na etapie mechanicznego odczytu, a ich długość jest nieporównywalnie mniejsza od długości rekonstruowanej sekwencji. Proces asemblacji, przy obecnym stanie techniki stanowi zatem jedyny możliwy automatyczny sposób uzyskania sekwencji odczytywanych genomów w postaci ciągłej. Praca stanowi szerokie omówienie nowego algorytmu asemblacji GRASShopPER, współautorem którego jest autor pracy. Główny wkład autora, oprócz samej idei kryjącej się za metodą, dotyczy dwóch podprocedur GRASShopPERa: kroku znajdowania znaczących rozwidleń grafu nałożeń oraz metody składania konsensusu w procedurze progresywnego dopasowania sekwencji.
EN Assembly can be perceived as a joint venture of computer science, biology, chemistry and medicine. Aim of the assembly problem is to find shortest common superstrings (contigs) built upon a given known set of sequences, called reads. Although the problem can be seen more general, we can assume reads come from intensive genetic material scan. The problem is very practical as at the current level of technology machines that provide reads, known as sequencers, are unable to determine entire sequence of a genome. Instead they provide relatively short genome fragments, though densely covering the genome. The thesis discusses the new approach to de novo assembly taking use of Overlap-Layout-Consensus strategy to provide high quality results, but taking advantage of a new technologies like GPUs to make it as efficient as possible. The main authors contribution to the method, apart from co-authorship of an idea behind the method itself, is a creation of its two core subrutines: overlap graph traversal step and the consensus alignment agreement phase.
158
computer sciences and computer science
computer science
DrOIN 1969
public
Norbert Dojer
Warszawa, Polska
22.03.2019
polish
public
Franciszek Seredyński
Warszawa, Polska
15.01.2019
polish
public
dissertation
Poznań, Polska
18.04.2019
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności: bioinformatyka