Pronalaženje varijanti gena grupiranjem pomoću algoritama dinamičkog programiranja

undergraduate thesis

• Title (english): Discovering Gene Variants Using Clustering and Dynamic Programming Algorithms
• Author: Nera Frajlić
• Mentor: Krešimir Križanović (mentor)
• Committee member: Krešimir Križanović (predsjednik povjerenstva)
• Committee member: Mile Šikić (član povjerenstva)
• Committee member: Robert Vaser (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-09-04, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Aleli su inačice gena koje se kod većine višestaničnih organizama nalaze na istom mjestu u homolognim parovima kromosoma. Par alela čini nasljednu osobinu. Poznavanje inačica pojedinog gena vrlo je korisno, no alele nije uvijek jednostavno prepoznati u uzorku. Pojedini aleli mogu biti slabo zastupljeni u populaciji, pa tako i u uzorku za istraživanje. Cilj ovog rada je razviti metode i algoritme grupiranja za prepoznavanje različitih alela u uzorku sekvenciranih gena MHC jelena običnog. Implementirana su četiri algoritma u programskom jeziku C++ koristeći alate Spoa i bioparser te algoritme dinamičkog programiranja međusobnog poravnanja sekvenci. Uzorci gena promatrani u radu dobiveni su sekvenciranjem metodom Ion Torrent i pohranjeni u datotekama FASTQ formata. U radu su opisani spomenuti algoritmi i rezultati dobiveni koristeći raspoložive podatke. Metode uspješno detektiraju vrlo zastupljene alele u uzorcima te ilustriraju probleme koji nastaju pri određivanju slabo zastupljenih alela kao i prisutnosti nevažećih podataka u uzorku.

Abstract (english)

Alleles are gene variants found at the same place in homologous chromosome pairs in most multicellular organisms. A pair of alleles constitutes a hereditary trait. Knowing the variants of a particular gene is very useful, but alleles are not always easy to recognize in a sample. Particular alleles may be poorly represented in the population, thus in the research sample. The aim of this paper is to develop clustering methods and algorithms for detecting different alleles in a sample of sequenced MHC deer genes. Four algorithms were implemented using C++ programming language, spoa and bioparser tools, as well as dynamic programming algorithms for pairwise sequence alignment. The gene samples observed in the paper were obtained using Ion Torrent sequencing method and stored in FASTQ format files. The paper describes the mentioned algorithms and the results obtained using available data. The methods successfully detect highly represented alleles in the sample and illustrate the problems which arise when determining poorly represented alleles as well as the presence of invalid data in the sample.

• Keywords: alel; gen; grupiranje; poravnanje; dinamičko programiranje; C++; Spoa
• Keywords (english): allele; gene; clustering; alignment; dynamic programming; C++; Spoa
• Language: croatian
• URN:NBN: urn:nbn:hr:168:150097
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 08:46:20