Short Reads Mapping

Kratka očitanja se većinom koriste u slučaju kada imamo već poznati, referentni genom neke vrste ili referencu, i želimo utvrditi razlike između reference i pojedine jedinke koju sekvenciramo. U ovom radu razvijena je metoda mapiranja kratkih očitanja na referencu koja je podijeljena na dvije faze. Prva faza sastoji se od indeksiranja kratkih podnizova na referenci i pronalaska kandidatnih pozicija pomoću zajedničkih podnizova na referenci i očitanjima te algoritma za traženje najdulje zajedničke podsekvence. U drugoj fazi koristi se KSW2 algoritam za određivanje optimalnog poravnanja dva niza. Provedeno je ispitivanje rješenja na stvarnim podatcima koje je pokazalo da bi se uz određena poboljšanja metoda mogla mjeriti s trenutno korištenim metodama. Implementacija je napisana u jeziku C/C++, a izvorni kod dostupan je na https://github.com/lbcb-edu/BSc-thesis-18-19/tree/spavlic.Short reads are mostly used when we already have a known reference genome of a species, and we want to determine the differences between the reference and the individual being sequenced. In this thesis, a method for mapping short reads consisting of two phases was developed. The first phase includes indexing short substrings of the reference and finding candidate positions using substrings that are in common to the reference and the read, with the help of the longest common subsequence algorithm. In the second phase the KSW2 algorithm is used for determining the optimal alignment of the two sequences. The solution was tested on a real-world dataset which showed that with some improvements, the method might be able to rival the methods that are currently in use. The implementation was written in C/C++ and the source code is available at https://github.com/lbcb-edu/BSc-thesis-18-19/tree/spavlic