Naslov
Landau-Vishkin-Nussinov algoritam za poravnanje dva niza
(Landau-Vishkin-Nussinov Algorithm for Pair-wise Sequence Alignment)

Autori
Vršnak, Donik

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
03.07

Godina
2018

Stranica
39

Mentor
Šikić, Mile

Ključne riječi
bioinformatika, Landau-Viskin-Nussinov, edlib, poravnanje nizova, Levenshteinova udaljenost
(bioinformatics, Landau-Vishkin-Nussinov, edlib, pair-wise sequence alignment, Levenshtein’s distance)

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.

Izvorni jezik
Hrvatski

POVEZANOST RADA