Pengkontruksian Bidirected Overlap Graph untuk Perakitan Sekuens DNA

Penulis

Wisnu Ananta Kusuma, Albert Adrianus

Abstrak

De novo DNA (Deoxyribonucleic Acid) sequence assembly atau perakitan sekuens DNA secara De novo adalah tahapan yang sangat penting dalam analisis sekuens DNA. Tahapan ini diperlukan untuk merakit atau menyambungkan kembali fragmen-fragmen DNA (reads) yang dihasilkan oleh Next Generation Sequencing menjadi genom yang utuh. Masalah perakitan DNA ini dapat direpresentasikan sebagai masalah Shortest Common Superstring (SCS). Perakitan ini memerlukan bantuan perangkat lunak untuk mendeteksi daerah yang sama pada reads DNA (overlap), mengkonstruksi overlap graph, dan kemudian mencari shortest path dari graf yang terbentuk. Metode ini dinamakan Overlap Layout Consensus (OLC). Hal yang penting dalam metode OLC adalah pendeteksian overlap dari masing-masing reads. Pada penelitian ini dikembangkan suatu teknik untuk membuat bidirected overlap graph. Suffix array digunakan untuk menentukan bagian overlap dari setiap reads dengan melakukan pengindeksan setiap suffix dari reads. Proses perakitan sekuens DNA merupakan suatu proses komputasi yang intensif. Untuk mengefisiensikan  proses dilakukan perubahan masing-masing suffix dan prefix menjadi suatu nilai tertentu yang bersifat tunggal dan mencari overlap dengan membandingkan angka yang merupakan representasi dari setiap reads. Cara ini lebih efisien dibandingkan melakukan pendeteksian overlap dengan metode pencocokan  string. Hasil perbandingan menunjukkan bahwa waktu yang diperlukan untuk mengeksekusi metode yang diusulkan (perbandingan angka) jauh lebih singkat dibandingkan dengan menggunakan metode pencocokan string. Untuk jumlah reads 2000 dan 5000 reads teknik yang diusulkan ini dapat menghasilkan overlap graph yang 100% akurat di mana semua reads dapat direpresentasikan ke dalam node yang dikonrtruksi dan semua overlap dapat direpresentasikan ke dalam edge.

 

Abstract

De novo DNA sequence assembly is the important step in DNA sequence analysis. This step is required for assembling fragments or reads produced by Next Generation Sequencing to yield a whole genome. The problem of DNA assembly could be represented as the Shortest Common Superstring (SCS) problem. The assembly requires a software for detecting the overlap region among reads, constructing an overlap graph, and finding the shortest path from the overlap graph.. This method is popular as The Overlap Layout Consensus (OLC). The most important step in OLC is detecting overlaps among reads. This study develop a new approach to construct bidirected overlap graph. Suffis array is used for detecting overlap region from each reads by indexing suffix of each reads. DNA assembly process is computational intensive. To reduce the execution time suffix and prefix was converted into the single value so that the detection of overlap could be done by comparing the values. This method is much more efficient compared to that of using string matching. Using 2000 and 5000 reads, the proposed method (value comparison) could yield the perfect overlap graph, in which all reads and overlap could be represented as nodes and edges, respectively. 

 

Teks Lengkap:

PDF

Referensi


ABEGUNDE, T., 2010. Comparison of DNA sequence assembly algorithms using mixed data sources [tesis]. Saskatoon (CA): University of Saskatchewan.

BATZOGLOU, S., JAFFE, D.B., STANLEY, K. et. al., 2002. ARACHNE: A whole genome shotgun assembler. Genome Res. 12: 177-189

BRENNER, S., JOHNSON, M., BRIDGHAM, J., GOLDA, G., LLOYD D.H., JOHNSON, D., LUO, S.J., McCURDY, S., FOY, M., EWAN, M., et al., 2000. Gene expression analysis by massively parallel signature sequencing (MPPS) on microbead arrays. Nat Biotechnol. 18:630-634.

CHAISSON, M., PEVZNER, P., TANG, H.. 2004. Fragment assembly with short reads. Bioinformatics. 20(13):2067-2074.

COMMINS, J., TOFT, C., FARES, M.A., 2009. Computational Biology Methods and Their Application to the Comparative Genomics of Endocellular Symbiotic Bacteria of Insects. Biol Proced Online. 11:52-78. doi: 10.1007/s12575-009-9004-1.

HERNANDEZ, D., FRANCOIS, P., FARINELLIi, Østerås M., SCHRENZEL, J., 2008. De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computer. Genome Res. 18:802-809

HUANG, X., WANG, J., ALURU, S., YANG, S., HILLIER, D., 2003. PCAP: A whole-genome assembly program. Genome Res. 13: 2164-2170

KUSUMA, W.A., ISHIDA, T., AKIYAMA, Y., 2011. A combined approach for de novo DNA sequence assembly of very short reads. IPSJ Transaction on Bioinformatics. 3(10):21-33. doi: 10.2197/ipsjtbio.4.21.

MANBER, U., MYERS, E.W., 1993. Suffix arrays: a new method for on-line string searches. SICOMP. 22(5):935-948.

MULLIKIN, J.C., NING, Z., 2003. The Phusion assembler. Genome Res. 13:81-90

MYERS, E.W., SUTTON, G.G., DELCHER, A.L., et. al., 2000. A whole-genome assembly of Drosophila. Science. 287: 2196-2204

POP, M., 2009. Genome assembly reborn: recent computational challenges. Briefing in Bioinformatics. 3(7):47-54

RICHTER, D.C., OTT, F., AUCH, A.F., SCHMID, R., HUSON, D.H., 2008. Metasim-A sequencing simulator for genomics and metagenomics. PLoS ONE. 3(10): e3373

ZHOU, X., REN, L., MENG, Q., LI, Y. YU, Y., YU, J., 2010. The next-generation sequencing techmology and application. Protein Cell. 1(6): 520-536




DOI: http://dx.doi.org/10.25126/jtiik.2020722070