Brzo pretraživanje sličnih proteinskih sljedova

undergraduate thesis

• Title (english): Fast Protein Sequence Similarity Search
• Author: Dario Babojelić
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Krešimir Križanović (član povjerenstva)
• Committee member: Robert Vaser (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Pretraga baza proteinskih sljedova jedan je od glavnih problema bioinformatike. Do sada su razmatrane razne determinističke i heurističke metode za rješavanjeovog problema. Determinističke metode daju optimalne rezultate, ali su vrlo spore. Heurističke metode mnogo su brže, ali ne pronalaze optimalne rezultate. Eksponencijalni rast broja proteinskih sljedova prisilio nas je da više istražujemo heurističke metode.

U ovom radu predstavljamo heuristički algoritam za efikasno pretraživanje baze proteinskih sljedova. Algoritam je implementiran u dva koraka. U prvom koraku koristimo heurističku metodu predstavljenu u radu Minimap (Li, 2016.) kako bi znatno smanjili prostor pretrage. U drugom koraku koristimo OPAL, knjižnicu koja nam pruža implementacije algoritama optimalnog poravnanja.

Abstract (english)

Protein database search is one of the fundamental problems in bioinformatics. For decades, it has been explored and solved using different exact and heuristic approaches. Deterministic approaches yield optimal result but are really slow. Heuristic approaches are a lot faster but don't find optimal result. Exponential growth of data in recent years has forced us to explore mostly heuristic approaches.

In this paper we present heuristic algorithm for efficient protein database search. Algorithm was implemented as a two-step approach. In the first step we use heuristic method introduced in Minimap (Li, 2016.) to significantly reduce database size. In the second step we use OPAL, a library which provides implementation of optimal alignment algorithms.

• Keywords: bioinformatika; heuristički algoritmi; baza proteinskih sljedova
• Keywords (english): bioinformatics; heuristic algorithm; protein database
• Language: croatian
• URN:NBN: urn:nbn:hr:168:820492
• 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: 2019-03-13 18:42:58