Pengkontruksian Bidirected Overlap Graph untuk Perakitan Sekuens DNA
DOI:
https://doi.org/10.25126/jtiik.2020722070Abstrak
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.
Downloads
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
Unduhan
Diterbitkan
Terbitan
Bagian
Lisensi
Artikel ini berlisensi Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
Penulis yang menerbitkan di jurnal ini menyetujui ketentuan berikut:
- Penulis menyimpan hak cipta dan memberikan jurnal hak penerbitan pertama naskah secara simultan dengan lisensi di bawah Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) yang mengizinkan orang lain untuk berbagi pekerjaan dengan sebuah pernyataan kepenulisan pekerjaan dan penerbitan awal di jurnal ini.
- Penulis bisa memasukkan ke dalam penyusunan kontraktual tambahan terpisah untuk distribusi non ekslusif versi kaya terbitan jurnal (contoh: mempostingnya ke repositori institusional atau menerbitkannya dalam sebuah buku), dengan pengakuan penerbitan awalnya di jurnal ini.
- Penulis diizinkan dan didorong untuk mem-posting karya mereka online (contoh: di repositori institusional atau di website mereka) sebelum dan selama proses penyerahan, karena dapat mengarahkan ke pertukaran produktif, seperti halnya sitiran yang lebih awal dan lebih hebat dari karya yang diterbitkan. (Lihat Efek Akses Terbuka).
