Pengkontruksian Bidirected Overlap Graph untuk Perakitan Sekuens DNA

Abstract

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