Landau-Vishkin-Nussinov algoritam za poravnanje dva niza

završni rad

• Naslov (engleski): Task: Landau-Vishkin-Nussinov Algorithm for Pair-wise Sequence Alignment
• Autor: Donik Vršnak
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Krešimir Križanović (č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: 2018-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Vremenska i memorijska složenost optimalnog poravnanja dva niza je kvadratna što za dulje nizove rezultira jako dugačkim vremenom izvršavanja. Međutim, često imamo informaciju o tome da su nizovi slični i možemo unaprijed ograničiti kolika će biti razlika među njima. U tom slučaju koristimo algoritme koji u matrici poravnanja računaju samo glavnu dijagonalu i određen broj susjednih. Jedan od najbržih takvih algoritama opisan je u radu "An efficient string matching algorithm with k differences for nucleotide and amino acid sequences". U ovome radu predstavljena je implementacija tog algoritma, te je algoritam prilagođen kako bi se mogao ugraditi u biblioteku edlib, gdje je zadužena za traženje poravnanja između kratkih nizova.

Sažetak (engleski)

Time and memory complexity of optimal pair-wise sequence alignment is quadratic, which, for longer sequences, results in very long computation time. However, we usually have the information that the sequences are similar and we can limit the maximal edit distance between them. In that case, we use algorithms which in the alignment matrix calculate only the main diagonal and a fixed number of neighboring diagonals. One of the fastest such algorithms is described in the paper titled "An efficient string matching algorithm with k differences for nucleotide and amino acid sequences". In this paper, we present an implementation of that algorithm, and we show how the algorithm was adapted to be included into edlib library, where it is used to determine pair-wise sequence alignment of shorter sequences.

• Ključne riječi: bioinformatika; Landau-Viskin-Nussinov; edlib; poravnanje nizova; Levenshteinova udaljenost
• Ključne riječi (engleski): bioinformatics; Landau-Vishkin-Nussinov; edlib; pair-wise sequence alignment; Levenshtein's distance
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:101555
• 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: 2019-03-14 02:05:26