FM-index based long reads error correction

Ovaj diplomski rad se bavi korištenjem FM-indeksa izgrađenog nad skupom kratkih očitanja u svrhu ispravljanja skupa dugih očitanja. Pomoću FM-indeksa implicitno se reprezentiraju svi de Bruijn grafovi za k-mer proizvoljne duljine. Pomoću 2 prolaska se ispravljaju duga očitanja, a zbog toga što su duga očitanja međusobno neovisna se ispravljanja mogu i paralelizirati. Prvi prolaz koristi manji k-mer i ispravlja većinu grešaka (orijentiranost na ispravak detalja), dok drugi prolaz koristi duži K-mer i ispravlja dugačke i/ili repetitivne regije. Nakon ispravljanja dugačkih očitanja, ona su puno veće točnosti, te se mogu dalje koristiti za sastavljanje genoma, koje je puno jednostavnije i efektivnije uspoređeno sa sastavljanjem genoma s kratkim očitanjima.This master’s thesis focuses on using an FM-index (built from a short read dataset) for correcting the long read dataset. The FM-index implicitly represents all de Bruijn graphs for arbitrary length kmers. Each long read shall be corrected using two passes - one with a shorter kmer, and the other with a longer K-mer. Short k-mer passes will do most of the correction, as they can pinpoint and correct defects in detail, while long K-mers will correct long and repetitive regions. After both passes are done, the accuracy of the long reads is increased. Because the long read dataset is made up of many independent long reads, this process can be parallelised. The corrected long reads can now be successfully used in downstream applications, such as genome assembly. The important thing to note is that genome assembly is much faster, simpler and more effective using the long read dataset, as compared to using the short read dataset