Graf neuronske mreže za de novo sastavljanje genoma

undergraduate thesis

• Title (english): Graph Neural Networks for De Novo Genome assembly
• Author: Jan Kolić
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Rafael Josip Penić (član povjerenstva)
• Committee member: Filip Tomas (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Proces automatske rekonstrukcije sekvence genoma iz manjih sekvenci (očitanja) još uvijek nije potpuno usavršen. Jedan od problema je pojednostavljivanje grafa sastavljanja (strukture dobivene iz očitanja) tako da se može pronaći put kroz graf koji bi predstavljao cijelu sekvencu. U ovom radu, koristimo različite arhitekture graf neuronskih mreža (GCN, GAT, GraphSAGE, GatedGCN) za predviđanje koji bridovi grafa su dijelovi optimalnog puta kroz graf. Pokazujemo da se efikasnost modela podiže uporabom svojstava bridova i prenošenjem poruka u oba smjera usmjerenih bridova grafa. Najbolji u smislu točnosti, postotka lažno negativnih rezultata te F1 mjere se pokazao GatedGCN model, dok je najmanji postotak lažno pozitivnih postignut s GraphSAGE modelom.

Abstract (english)

The process of automatically reconstructing the full genome sequence, using smaller sequences called reads, hasn't yet been perfected. One of the problems is simplifying the assembly graph (a structure generated using the reads) so that a path through it, which represents the full sequence, can be found. In this paper, we train different graph neural network models (GCN, GAT, GraphSAGE, GatedGCN) to predict which edges are part of the optimal path through the graph. We show that bidirectional message passing (on a directed assembly graph) and using edge features improve the efficiency of the models. The GatedGCN models proved to be the best in terms of accuracy, false negative rate and F1 measure, while the GraphSAGE models produced the lowest false positive rates.

• Keywords: bioinformatika; de novo sastavljanje genoma; sastavljanje genoma; graf sastavljanja; graf neuronske mreže; sekvenciranje genoma; Hamiltonov put
• Keywords (english): bioinformatics; de novo genome assembly; genome assembly; assembly graph; graph neural network; genome sequencing; Hamiltonian path
• Language: english
• URN:NBN: urn:nbn:hr:168:586262
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-10-11 09:20:28