Master's Thesis

Whole genome alignment using suffix trees

Main document 3.4 MB Appendix 2.49 kB

FEKTMaster's ThesisStudent: Ing. Lukáš KloubaAcad. year: 2016/2017

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

Opponent: Mgr. Ing. Karel Sedlář

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.

Language

Czech

State

Defended (thesis was successfully defended)

Hodnocení známka

C

Faculty

Department

Study branch

Biomedical Engineering and Bioinformatics

Classification by leader
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.

final grade: B
final score: 80


Classification by opponent
Mgr. Ing. Karel Sedlář

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.

final grade: C
final score: 76


Literature

[1] UKKONEN, E. On-line construction of suffix trees. Algorithmica. 1995, 3, 249-260.
[2] DELCHER, A.L.; PHILLIPPY, A.; CARLTON, J.; SALZBERG, S.L. Fast algorithm for large-scale genome alignment and comparison. Nucleic Acids Research. 2002, 30 (11), 2478-2483.

Keywords

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