Master's Thesis

Whole genome alignment using suffix trees

Final Thesis 3.4 MB Appendix 2.49 kB

Author of thesis: Ing. Lukáš Klouba

Acad. year: 2016/2017

Supervisor: Ing. Denisa Maděránková, Ph.D.

Reviewer: doc. Mgr. Ing. Karel Sedlář, Ph.D.

Abstract:

The aim of this thesis is to create an algorithm that allows the alignment of the genome
of two organisms by means of suffix structures and to implement it into the programming
language environment R. The thesis deals with the description of the construction of the
suffix structures and the methods of whole genome alignment. The result of the thesis
is a functional algorithm for whole genome alignment by means of suffix structures
implemented in the software environment R and its comparison with similar programs
for the whole genome alignment.

Keywords:

suffix tree, suffix array, Ukkonen’s algorithm, R, whole-genome alignment

Date of defence

06.06.2017

Result of the defence

Defended (thesis was successfully defended)

znamkaCznamka

Grading

C

Process of defence

Student prezentoval výsledky své práce a komise byla seznámena s posudky. Ing. Maděránková položila otázku: Co to jsou treponemy? Doc. Kolář položil otázku: Jak je možné zrychlit navržený algoritmus? Student obhájil bakalářskou práci a odpověděl na otázky členů komise a oponenta.

Language of thesis

Czech

Faculty

Department

Study programme

Biomedical Engineering and Bioinformatics (BTBIO-F)

Field of study

Biomedical Engineering and Bioinformatics (F-BTB)

Composition of Committee

doc. Ing. Radim Kolář, Ph.D. (předseda)
doc. Mgr. Ctirad Hofr, Ph.D. (místopředseda)
doc. RNDr. Martin Kovár, Ph.D. (člen)
Ing. Marina Filipenská, Ph.D. (člen)
Ing. Denisa Maděránková, Ph.D. (člen)
Ing. Vratislav Čmiel, Ph.D. (člen)

Supervisor’s report
Ing. Denisa Maděránková, Ph.D.

Předložená diplomová práce je vypracována na 45 stranách textu od Úvodu po Závěr. Vlastní řešení tématu a výsledky jsou popsány na 19 stranách. V práci je citováno 21 literárních zdrojů, což je na diplomní práci menší počet, ale všechny zdroje jsou hodnotné cizojazyčné odborné publikace.
Po formální stránce je práce až na některé nedostatky na dobré úrovni. Mezi nedostatky patří např.: některé obrázky nejsou zmíněny v textu; některé vývojové diagramy jsou zbytečně moc velké; latinské názvy organismů nejsou psány kurzívou; u obrázků 5.3 až 5.8 není explicitně napsáno, co jsou sekvence 1 a 2, zvláště z toho důvodu, že sekvence 1 má u různých obrázků různé délky.
Konzultací student využíval méně a spíše až ke konci semestru.
Teoretická část práce je přehledně a kvalitně zpracována. Oceňuji konkrétní příklady stromů a polí a přehledné vývojové diagramy. Přehledně je také popsáno vlastní programové řešení.
Ačkoliv se student potýkal s problémy spojenými s horší optimalizací programového prostředí R pro velké výpočty, jeho řešení konstrukce sufixových polí a porovnávání dvou sekvencí je hodnotné. Všechny body zadání byly splněny. Points proposed by supervisor: 80
Display more

Grade proposed by supervisor: B

Student Lukáš Klouba se ve své práci zabývá náročným úkolem zarovnávání dlouhých sekvencí. Ve své práci nejprve pojednává o sufixových stromech a polích, které pro jejich výhodnější vlastnosti nakonec použil pro návrh vlastního přístupu a následně o algoritmech pro celogenomové zarovnání. Navazuje praktickou částí, kde popisuje vytvořený algoritmus, který porovnává s algoritmy již dostupnými. Až na drobný nedostatek v tom, že na značnou část obrázků a výpisů chybí v textu odkaz, je práce velmi přehledná, a to díky logickému členění a studentově průběžné diskusi jednotlivých témat. Prací se ovšem prolíná systematická chyba, která může za problémy, se kterými se student potýkal v praktické části. Souhlasím, že jazyk R/Bioconductor není na podobný úkol ideální, je však nutné si uvědomit, že se jedná o plnohodnotný jazyk, který má své určité vlastnosti, a ne o programové prostředí s neodladěnými cykly, jak student v práci uvádí. Se standardními třídami R pracuje na principu pass-by-value, při použití for cyklu je tak argument pokaždé kopírován v paměti a implementace je tak velmi neefektivní. To lze ovšem obejít několika způsoby, např. kompilací části kódu pomocí C++, které pracuje na principu pass-by-reference, s využitím balíčku Rcpp. Oceňuji však přístup studenta, který problém vyřešil vlastním návrhem algoritmu postaveného na sufixových polích. Při testování algoritmu se pak kromě zarovnávání celých genomů zabývá i otázkou vyhledávání genů, zde mi chybí srovnání s algoritmem BLAT, který mi na tento typ úkolu připadne nejvhodnější. Zadání práce však považuji za splněné a díky diskusi výsledků i teoretických předpokladů práci po odborné stránce za velmi dobrou. Kvůli formálním nedostatkům jako je množství gramatických chyb, špatně odsazených odstavců za nadpisy a především na magisterský stupeň studia nedostatečnou prací s literaturou (nejednotný styl citací, reference za celé odstavce, chybějící reference u zmíněných nástrojů a celkově malý počet referencí), hodnotím celkově práci pouze jako dobrou. Points proposed by reviewer: 76
Display more

Grade proposed by reviewer: C