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

master's thesis

• Title (english): FM-index based long reads error correction
• Author: Kristijan Čeple
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Ivica Botički (član povjerenstva)
• Committee member: Danijel Mlinarić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-02-23, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: FM indeks; de Bruijn graf; sekvenciranje; sastavljanje genoma; duga očitanja; kratka očitanja; dugo očitanje; kratko očitanje; FMLRC; kmer
• Keywords (english): FM-index; de Bruijn graph; sequencing; genome assembly; long read; short read; FMLRC; kmer
• Language: croatian
• URN:NBN: urn:nbn:hr:168:246578
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:00:11