Kompresia biologických sekvencií

• Thesis title in thesis language (Slovak): Kompresia biologických sekvencií
• Thesis title in Czech: Kompresia biologických sekvencií
• Thesis title in English: Compression of biological sequences
• Key words: bioinformatika, kompresia, DNA, SAM formát
• English key words: bioinformatics, compression, DNA, SAM format
• Academic year of topic announcement: 2011/2012
• Thesis type: diploma thesis
• Thesis language: slovenština
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: RNDr. František Mráz, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 24.02.2012
• Date of assignment: 17.04.2012
• Confirmed by Study dept. on: 20.04.2012
• Date and time of defence: 03.09.2012 09:30
• Date of electronic submission: 12.07.2012
• Date of submission of printed version: 12.07.2012
• Date of proceeded defence: 03.09.2012
• Opponents: doc. RNDr. Tomáš Dvořák, CSc.

Guidelines

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.

References

[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.