Korištenje graf neuronskih mreža za odvajanje haplotipa u grafovima sastavljanja

master's thesis

• Title (english): Using Graph Neural Networks to Separate Haplotypes in Assembly Graphs
• Author: Filip Wolf
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Mario Brčić (član povjerenstva)
• Committee member: Krešimir Križanović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Razdvajanje haplotipa je bitan zadatak u bioinformatici s raznim primjenama u stvarnom svijetu. Tradicionalno, za rješavanje ovoga zadatka su korištene razne heuristike i ručno rađeni algoritmi. S nedavnim usponom algoritama dubokog učenja, specifično, Graf Neuronskih Mreža, ostaje velika praznina u istraživanju koju treba ispuniti poboljšanjem algoritama. Primjenjujemo Graf Neuronske Mreže za razdvajanje haplotipa na podatcima kvasca i naši rezultati na sintetičkim podacima su uspješni, time dokazujući snagu ove metode. Najbolji model, Graf Neuronska Mreža s Pažnjom na Bridovima je imala F1-vrijednost od 85.13%, pri čemu je jedan haplotip bio gotovo savršeno odvojen, a problemi su se javljali samo kod drugoga zbog visoke fragmentacije. Model je koristio mehanizam pažnje na značajkama i čvorova i bridova da bi iskoristio sve dostupne podatke u grafu. Na žalost, mnogo problema i dalje nije riješeno, gdje je najveći problem neispravni proces stvaranja podataka haplotipa. Ipak, ovaj rad otvara razne puteve istraživanja za ovu temu i daje korisnu bazu.

Abstract (english)

Haplotype separation is an important task in bioinformatics with numerous real-world applications. Traditionally, heuristics and hand-crafted algorithms were used for solving it. With the recent rise in deep learning algorithms, specifically, Graph Neural Networks, there remains a large gap in research to be filled with algorithm improvement. We employ Graph Neural Networks for haplotype separation on yeast data and our results on synthetic data are a success, proving the merit of the method. The best model, the Edge Graph Attention Network model, had an F1-score of 85.13%, with one haplotype being almost perfectly separated, and problems arising only on the second one due to high fragmentation. It employed the attention mechanism on both node and edge features to leverage all data available in a graph. However, many issues arise that remain to be solved, the main one being the faulty haplotype data generation process. Nevertheless, this work opens up numerous alleyways of further research into the topic and offers a useful baseline.

• Keywords: Bioinformatika; Graf Neuronske Mreže; GNN; Odvajanje haplotipa; Duboko Učenje; Strojno Učenje
• Keywords (english): Bioinformatics; Graph Neural Networks; GNN; Haplotype Separation; Deep Learning; Machine Learning
• Language: english
• URN:NBN: urn:nbn:hr:168:529895
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 22:02:28