ABSTRAKSI: Multiple sequence alignment merupakan salah satu masalah fundamental pada bidang bioinformatika karena merupakan langkah awal untuk menganalisa phylogenetics tree organisme, memprediksi struktur kedua dan ketiga dari protein dan RNA, dan lain sebagainya. Sejumlah metode dan pendekatan telah dipublikasikan selama lebih dari 30 tahun terakhir. Namun belum ada satu tool pun yang dapat secara mangkus menyelesaikan masalah multiple sequence alignment.
Metode dynamic programming telah terbukti dapat menangani masalah pairwise sequence alignement secara efektif dan efisien baik pada global, maupun local alignment. Namun, ketika dikembangkan untuk menangani multiple sequence alignment, metode dynamic programming membutuhkan resource yang sangat besar.
Untuk itu, pada tugas akhir ini, digunakan metode divide-and-conquer untuk mengefisiensikan memory yang digunakan dynamic programming untuk melakukan multiple sequence alignment.
Dengan menerapkan metode divide-and-conquer, kompleksitas ruang untuk melakukan multiple sequence alignment dapat berkurang dari Ο(nmk), dimana nm merupakan panjang maksimum sequence awal dan k merupakan banyaknya sequence yang di-align, menjadi Ο(ńmk), dimana ńm merupakan batas panjang maksimum sequence yang diperbolehkan. Namun, akibat penggunaan divide-and-conquer, hasil alignment menjadi tidak optimal (approximate). Untuk memperbaiki hasil alignment agar kembali optimal, digunakan iterative refinement. Kompleksitas ruangnya kemudian menjadi Ο(Lk), dimana L merupakan limit yang digunakan.Kata Kunci : Bioinformatika, multiple sequence alignment, global sequence alignment, Efisiensi memory, optimasi, exact method, dynamic programming, divide-and-conquer, iterative refinement.ABSTRACT: Multiple sequence alignment is the most fundamental problem in bioinformatics research field because it is the first step to analyze organism phylogenetic tree, secondary and tertiary structure prediction of protein and RNA, etc. various of methods and approachs have been published for over the last 30 years. But there is no method that can solve the problem of multiple sequence alignment efficiently and optimally.
Dynamic programming method has been proven to handle pairwise sequence alignment effective and efficiently at both global and local alignment. However, when developed to handle multiple sequences alignment, it often to fail because the requirement of very large resource.
Therefore, in this final, the divide-and-conquer method adapted to make the memory used by dynamic programming to solve multiple sequence alignment problems more efficient.
By applying divide-and-conquer method, the time and space complexity to perform multiple sequence alignment can be reduced from Ο(nmk), where nm is the maximum length of initial sequence and k is the number of sequences that want to be aligned, to Ο(ńmk), where ńm is the limit of allowed sequence length. However, due to the use of divide-and-conquer, the resulting alignment becomes unoptimal (approximate). To improve the resulting alignment back to optimum, iterative refinement adapted. The space complexity than become Ο(nmk), where L is the limit used.Keyword: Bioinformatics, multiple sequence alignment, global sequence alignment, memory efficiency, optimization, exact method, dynamic programming, divide-and-conquer, iterative refinement.