Using Graph Neural Networks to Separate Haplotypes in Assembly Graphs

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.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