Ispravak pogrešaka u dugačkim očitanjima korištenjem FM-indeksa

diplomski rad

• Naslov (engleski): FM-index based long reads error correction
• Autor: Kristijan Čeple
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Ivica Botički (član povjerenstva)
• Član povjerenstva: Danijel Mlinarić (č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: 2023-02-23, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: FM indeks; de Bruijn graf; sekvenciranje; sastavljanje genoma; duga očitanja; kratka očitanja; dugo očitanje; kratko očitanje; FMLRC; kmer
• Ključne riječi (engleski): FM-index; de Bruijn graph; sequencing; genome assembly; long read; short read; FMLRC; kmer
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:246578
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:00:11