Zapisivanje sličnih sekvenci u obliku grafa

završni rad

• Naslov (engleski): Storing Similar Sequences in Graph Format
• Autor: Lucija Strejček
• Mentor: Krešimir Križanović (mentor)
• Član povjerenstva: Krešimir Križanović (predsjednik povjerenstva)
• Član povjerenstva: Filip Bosnić (član povjerenstva)
• Član povjerenstva: Josip Marić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-02, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Poravnanje više sekvenci jedan je od najvažnijih alata u bioinformatici i ima dugu povijest istraživanja u računarstvu i bioinformatici. Proizvedeni podatci sekvenciranja najčešće predstavljaju sekvence DNA, RNA i proteina te je od velike važnosti pronaći način pohrane takvih sekvenci koji će zahtijevati manje diskovnog prostora, ali omogućiti efikasno pretraživanje. Rješenje problema je pohrana više sekvenci pomoću grafa poravnanja parcijalnog uređaja (POA). Prvi korak prilikom poravnanja više sekvenci je izgradnja grafa iz prve zadane sekvence tako da svako slovo sekvence predstavlja jedan čvor. Zatim se svaka sljedeća sekvenca poravnava na taj graf koristeći modificirani Needleman-Wunch algoritam gdje svaki čvor ovisi o svim svojim prethodnicima u grafu. Ovdje je predstavljen algoritam poravnanja sličnih sekvenci u obliku grafa poravnanja parcijalnog uređaja koji omogućuje jednostavnije i točnije poravnanje više sekvenci te poravnanje nove sekvence na postojeći graf.

Sažetak (engleski)

Multiple sequence alignment is one of the most important tools in bioinformatics and has a long history of research in computing and bioinformatics. The produced sequencing data most often represent DNA, RNA and protein sequences, and it is of great importance to find a way to store such sequences that will require less disk space, but allow efficient search. The solution is to store multiple sequences using a partial order alignment graph (POA). The first step in aligning multiple sequences is to construct a graph from the first given sequence so that each letter of the sequence represents one node. Then each subsequent sequence is aligned to that graph using a modified Needleman-Wunch algorithm where each node depends on all its predecessors in the graph. Here, a sequence alignment algorithm in the form of a partial order alignment graph is presented, which enables simpler and more accurate alignment of multiple sequences and alignment of a new sequence to an existing graph.

• Ključne riječi: bioinformatika; POA; Needleman-Wunsch; konsenzus
• Ključne riječi (engleski): bioinformatics; POA; Needleman-Wunsch; consensus
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:142406
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 21:43:04