Pengkonstruksian Bidirected Overlap Graph Untuk DNA Sequence Assembly

Abstract

DNA sequencing technologies dapat digunakan untuk memecah gen bakteri menjadi jutaan potongan kecil yang disebut reads. Namun demikian, reads tersebut perlu disambung menjadi contigs agar dapat digunakan. Terdapat 2 metode untuk menyambungkan reads. Yang pertama dengan menggunakan overlap layout consensus (OLC) dan yang lainnya dengan menggunakan de Bruijn graph. Hal penting dalam metode OLC adalah bagian overlap dari masing-masing reads. Pada penelitian ini dikembangkan sebuah sistem untuk membuat bidirected overlap graph yang nantinya akan menghitung berapa jumlah reads yang saling overlap satu sama lain. Suffix array digunakan untuk menentukan fase/bagian overlap dari setiap reads dengan mengindeks setiap suffix dari reads. Waktu adalah parameter penting dalam DNA assembly karena DNA assembly membutuhkan banyak waktu. Untuk mengurangi waktu dilakukan perubahan dari masing-masing suffix dan prefix menjadi suatu nilai tertentu yang bersifat tunggal dan mencari overlap dengan membandingkan setiap reads. Cara ini memberikan dampak positif daripada perbandingan dengan menggunakan string. Perbandingan waktu yang diperlukan antara perbandingan angka dan perbandingan string cukup signifikan. Untuk 2000 dan 5000 reads, sistem dapat memberikan hasil 100% akurat untuk jumlah node dan edge