Kompresia biologických sekvencií

• Název práce v jazyce práce (slovenština): Kompresia biologických sekvencií
• Název práce v češtině: Kompresia biologických sekvencií
• Název v anglickém jazyce: Compression of biological sequences
• Klíčová slova: bioinformatika, kompresia, DNA, SAM formát
• Klíčová slova anglicky: bioinformatics, compression, DNA, SAM format
• Akademický rok vypsání: 2011/2012
• Typ práce: diplomová práce
• Jazyk práce: slovenština
• Ústav: Katedra softwaru a výuky informatiky (32-KSVI)
• Vedoucí / školitel: RNDr. František Mráz, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 24.02.2012
• Datum zadání: 17.04.2012
• Datum potvrzení stud. oddělením: 20.04.2012
• Datum a čas obhajoby: 03.09.2012 09:30
• Datum odevzdání elektronické podoby: 12.07.2012
• Datum odevzdání tištěné podoby: 12.07.2012
• Datum proběhlé obhajoby: 03.09.2012
• Oponenti: doc. RNDr. Tomáš Dvořák, CSc.

Zásady pro vypracování

Objem dát získavaných sekvenovacími technológiami novej generácie rastie podstatne rýchlejšie ako kapacity úložných médií. Výstupy sekvenátorov okrem samotných prečítaných krátkych úsekov DNA obsahujú ďalšie informácie napr. o spoľahlivosti/kvalite čítania každého symbolu DNA. Takéto dáta je treba i po zostavení sekvencie kompletného genómu ďalej uchovávať. Faktickým štandardom v tejto oblasti sa v posledných rokoch stal formát SAM (Sequence Alignment/Mapping Format) a jeho binárna komprimovaná verzia BAM. Súbor vo formáte SAM/BAM sa používa ako formát zostavenia sekvencie so zachovaním dát získaných zo sekvenátora a ďalších metainformácií. Tento formát umožňuje pomocou indexu náhodný prístup do celého zostavenia. To je nutné, pretože súbory SAM/BAM dosahujú gigabytové veľkosti a manipulácia s celým súborom naraz je náročná na čas a hardware počítača.

Cieľom práce je navrhnúť lepšiu bezstratovú kompresnú schému súborov vo formáte SAM tak, aby komprimovaný súbor bol čo najmenší, ale zostala zachovaná možnosť priameho prístupu do pôvodného SAM súboru. Navrhnutá metóda bude predpokladať, že vstupný SAM súbor je "utriedený", tzn. že obsahuje zostavenie fragmentov DNA do výslednej sekvencie. Súčasťou práce bude určenie kompresných metód relevantných pre danú doménu, ich porovnanie pri kompresii súborov vo formáte SAM a implementácia platformovo nezávislého programu pre kompresiu a dekompresiu pre tento typ súborov.

Seznam odborné literatury

[1] H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan, N. Homer, G. Marth, G. Abecasis, R. Durbin, et al: The sequence alignment/map format and SAMtools. Bioinformatics, 25(16):2078, 2009.

[2] M.H.Y. Fritz, R. Leinonen, G. Cochrane, and E. Birney: Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome research, 21(5):734-740, 2011.

[3] M.N. Sakib, J. Tang, W.J. Zheng, and C.T. Huang: Improving Transmission Efficiency of Large Sequence Alignment/Map (SAM) Files. PloS one, 6(12):e28251, 2011.

[4] D. Salomon, G. Motta: Handbook of Data Compression, 5th edition. Springer, 2010.