Penerapan Algoritme Floyd Warshall untuk mencari Shortest Path pada Directed Overlap Graph

Abstract

Teknologi sequencing telah berkembang sejak tahun 1970. Teknologi sequencing menggunakan teknik shotgun untuk memotong genom menjadi banyak fragmen. Potongan-potongan fragmen akan disusun menjadi genom yang utuh dengan teknik assembly. Penelitian sebelumnya melakukan teknik assembly dengan pendekatan overlap-layout-consensus (OLC) sehingga didapatkan graf overlap. Hasil dari graf overlap akan dicari jalur terpendek untuk menemukan contigs (kumpulan reads). Teknik pencarian jalur terpendek dilakukan dengan menggunakan algoritme Floyd Warshall. Dari percobaan diperoleh kumpulan contigs dari beberapa nilai overlap yaitu 10, 15, 20, 25, dan 30 yang diuji dengan BLAST. Hasil uji BLAST berhasil mengidentifikasi data contigs sebagai neuclotide dari organisme Acidiphilium multivorum AIU301 plasmid pACMV4. Selain itu diperoleh data waktu eksekusi program berbanding terbalik dengan rata-rata dari setiap nilai overlap yang dimasukkan.