Pembentukan Overlap Graph Menggunakan Acgt Words Tree Pada Sekuens Dna

Abstract

DNA sequence assembly memiliki peran yang sangat penting dalam analisis genom. Salah satu metode yang digunakan dalam DNA sequence assembly untuk penggabungan potongan-potongan fragmen adalah overlap layout consensus. Teknik overlap layout consensus yang digunakan adalah overlap graph. Pada graf ini, node merepresentasikan fragmen dan edge merepresentasikan overlap. Penelitian ini mengembangkan sebuah perangkat lunak untuk menyusun overlap graph menggunakan ACGT words tree. Evaluasi dilakukan dengan menghitung waktu eksekusi yang kemudian dibandingkan dengan penyusunan menggunakan suffix tree dengan nilai 15, 20, dan 25 pada minimum overlap. Minimum overlap didefinisikan sebagai panjang minimum dari substring yang diperhitungkan dalam overlap di antara 2 fragmen. Hasil evaluasi menunjukkan bahwa penyusunan overlap graph menggunakan ACGT words tree memberikan nilai output pada waktu eksekusi yang lebih cepat dibandingkan dengan penyusunan overlap graph menggunakan suffix tree.