Zapisivanje sličnih sekvenci u obliku grafa

undergraduate thesis

• Title (english): Storing Similar Sequences in Graph Format
• Author: Lucija Strejček
• Mentor: Krešimir Križanović (mentor)
• Committee member: Krešimir Križanović (predsjednik povjerenstva)
• Committee member: Filip Bosnić (član povjerenstva)
• Committee member: Josip Marić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-02, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: bioinformatika; POA; Needleman-Wunsch; konsenzus
• Keywords (english): bioinformatics; POA; Needleman-Wunsch; consensus
• Language: croatian
• URN:NBN: urn:nbn:hr:168:142406
• 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-01-14 21:43:04