MULTIPLE SEQUENCE ALIGNMENT MENGGUNAKAN HIDDEN MARKOV MODEL DENGAN AUGMENTED SET DAN PENGARUHNYA TERHADAP AKURASI POHON FILOGENETIK

INTISARI
Task dasar dalam menganalisa data biologi molekuler diantaranya adalahmultiple sequence alignment (MSA) dan inferensi pohon filogenetik. Kualitas pohon filogenetik tergantung pada kualitas MSA. Hidden markov model(HMM) merupakan salah satu metode yang cukup baik untuk menghasilkan MSA, tetapi untuk sequencedengan similarityyang rendah, metode ini akan menghasilkan MSA yang kurang optimal .Dalam tesis ini, dilakukan penelitian terhadap alternatif yang dapatdilakukan dalam melakukan multiple alignmentterhadap sequence proteindengan similarityyang rendah menggunakan HMM, sehingga hasil MSA dapatdijadikan input dan menghasilkan pohon filogenetik yang lebih akurat.
Alternatifyang dilakukan adalah membangun augmented setdengan parameter berupajumlah child sequencedan prosentase mutasi yang dilakukan terhadap child sequence. Dilakukan dua jenis proses mutasi yaitu mutasi berdasar substituion matrixBLOSUM 80 dan mutasi secara random. Augmented setdijadikan input ke dalam HMM untuk mendapatkan MSA. Untuk mengestimasi parameter-parameter dalam HMM, digunakan algoritma pembelajaran Baum-Welch sedangkan untuk melakukan alignmentdari unaligned sequence, digunakan algoritma Viterbi. Prototype tooldibangun menggunakan bahasa pemrograman Java dan memanfaatkan libraryBiojava. Akurasi pohon filogenetik yang menggunakan MSA dengan augmented setdibandingkan dengan MSA tanpa augmented set. Terdapat dua metode inferensi pohon filogenetik yang digunakan dalam penelitian ini, pertama adalah neighbour joiningdengan toolClustalX , kedua metode parsimony dengan tool Phylip Protpars. Data yang digunakan adalah data sequenceasam amino ribosom 16S dari mitokondria. Hasil pengujian menunjukkan bahwa akurasi pohon filogenetik meningkat dengan menggunakan augmented setberdasar matrix BLOSUM 80 dan metode neighbour joiningyang memiliki kriteria jumlah sequencedan HDS yang sedikit, serta selisih panjang maksimal dan panjang rata-rata sequence-nya rendah. Sedangkan akurasi pohon filogenetik menggunakan augmented setdan metode parsimony meningkat atau menurun.
Kata kunci : MSA, Pohon Filogenetik, HMM, Augmented Set, SequenceRibosom

ABSTRACT
MULTIPLE SEQUENCE ALIGNMENT USING HIDDEN MARKOV MODEL WITH AUGMENTED SET AND ITS INFLUENCE ON PHYLOGENETIC ACCURACY
The basic tasks in molecular biology data analysis are multiple sequence alignment (MSA) and phylogenetic tree inference. The quality of the phylogenetic tree depends on the quality of the MSA. Hidden Markov model (HMM) is one of the good methods to generate the MSA, but having sequences with low similarity, this method will produce less optimal MSA. This research works on performing multiple alignments of protein sequences with low similarity using the HMM, which can be used as input and it produces more accurate phylogenetic tree. The research is carried out by building augmented set. The parameters are the number of child sequences and the percentage of mutation applied in child sequence. There are two kind of mutation process, first based on substitution matrix BLOSUM 80 and second, random mutation. Augmented set used as input into the HMM to obtain the MSA. Baum welch learning algorithm is used to estimate the parameters in HMM. While Viterbi algorithm is used to arrange the alignment from unaligned sequences. The prototype tool is built using Java programming language and utilizing Biojava library.
In this research, the accuracy of phylogenetic trees using MSA with augmented set is compared with the MSA without augmented set. There are two phylogenetic tree inference methods used in here. First, neighbour joining is conducted using ClustalX tool. Second, parsimony methods is conducted using Phylip Protpars tool. The data are the amino acid sequences of ribosomes 16S from mitochondria. The accuracy of phylogenetic tree using augmented set based on matrix BLOSUM 80 and the neighbour joining method increases when the datasets with criteria : the number of sequences and HDS (highly diverge sequence) are small enough, and the difference between maximum length and average length of sequences is small enough. While the accuracy of phylogenetic trees using the augmented set and the parsimony method can increase or decrease arbitrarily.
Keywords: MSA, Phylogenetic Trees, HMM, Augmented Set, Ribosomes 16S Protein Sequence

DAFTAR ISI
KATA PENGANTAR iii
DAFTAR ISI v
DAFTAR TABEL viii
DAFTAR GAMBAR x
INTISARI xii
ABSTRACT xiii
BAB I. PENDAHULUAN 14
1.1 Latar Belakang 15
1.2 Rumusan Masalah 15
1.3 Batasan Masalah 16
1.4 Tujuan Penelitian 16
1.5 Manfaat Penelitian 16
1.6 Keaslian Penelitian 16
1.7 Metode Penelitian 17
1.8 Sistematika Penulisan 18
BAB II. TINJAUAN PUSTAKA 19
BAB III. LANDASAN TEORI 21
3.1 Model Markov dan Hidden markov model 21
3.1.1 Model Markov 21
3.1.2 Hidden Markov Model 22
3.2 Multiple Sequence Alignmentdalam Bioinformatika 30
3.2.1 DNA dan gen 30
3.2.2 Protein 32
3.2.3 Alignment 33
3.3 Metode – Metode yang Digunakan pada Multiple Sequence Alignment 37
3.3.1 Dynamic programming 37
3.3.2 Progressive alignment 38
3.3.3 Metode iteratif 40
3.3.4 Algoritma genetika 41
3.3.5 Hidden markov model 41
3.4 Multiple Sequence Alignmentmenggunakan Hidden Markov Model 42
3.4.1 Arsitektur hidden markov modeluntuk MSA 42
3.4.2 Algoritma pembelajaran Baum Welch 44
3.4.3 Algoritma viterbi 63
3.4.4 Permasalahan pada training dengan algoritma Baum-Welch 69
3.5 Filogenetik 71
3.5.1 Pohon filogenetik 71
3.5.2 Phylogenetic inference 73
3.5.3 Perbandingan pohon filogenetik 74
3.6 Unified Modeling Language (UML) 75
3.6.1 Use Case Diagrams 76
3.6.2 Class Diagrams 77
BAB IV. ANALISIS DAN RANCANGAN SISTEM 79
4.1 Analisis Sistem 79
4.2 Deskripsi Sistem 80
4.2.1 HMM dengan augmented set 80
4.2.2 Data sequencedan pohon filogenetik 84
4.3 Spesifikasi Sistem 87
4.3.1 Activity diagram 90
4.3.2 Sequence diagram 93
4.3.3 Class diagram 97
4.3.4 Rancangan Diagram alir data 104
4.4 Rancangan Antarmuka 105
4.4.1 Panel welcome 105
4.4.2 Panel Augmenting 105
4.4.3 Panel MSA dengan HMM 107
4.5 Rancangan Pengujian 109
BAB V. IMPLEMENTASI 112
5.1 Pembangunan Sistem 112
5.2 Implementasi Algoritma 112
5.2.1 Algoritma augmenting set 113
5.2.2 Algoritma multiple alignmentdengan HMM 117
5.2.3 Prosedur Baum Welch Trainer 120
5.2.4 Prosedur Viterbi 121
5.3 Implementasi Aplikasi 122
5.3.1 Augmenting Set 123
5.3.2 Multiple Alignment 124
BAB VI. HASIL PENELITIAN DAN PEMBAHASAN 128
6.1 Data, Parameter dan Prosedur Pengujian 128
6.2 Hasil Pengujian 131
6.2.1 Pengujian menggunakan toolinferensi filogenetik ClustalX 133
6.2.2 Pengujian menggunakan toolinferensi filogenetik Phylip Protpars
BAB VII. PENUTUP 155
DAFTAR PUSTAKA 158
LAMPIRAN A. ISI SATU FILE SEQUENCEMITOKONDRIA 159
LAMPIRAN B. HASIL PENGUJIAN MENGGUNAKAN TOOL INFERENSI FILOGENETIK CLUSTALX DENGAN AUGMENTED SET BERDASAR BLOSUM 80 UNTUK DATASET DENGAN HDS 168
LAMPIRAN C. HASIL PENGUJIAN MENGGUNAKAN TOOLINFERENSI FILOGENETIK PHYLIP PROTPARS DENGAN
AUGMENTED SETBERDASAR BLOSUM 80 UNTUK DATASET DENGAN HDS 170
LAMPIRAN D. HASIL PENGUJIAN MENGGUNAKAN TOOL INFERENSI FILOGENETIK CLUSTALX DENGAN AUGMENTED SET TIDAK BERDASAR BLOSUM 80 UNTUK DATASET DENGAN HDS 172
LAMPIRAN E. HASIL PENGUJIAN MENGGUNAKAN TOOL INFERENSI FILOGENETIK CLUSTALX DENGAN AUGMENTED SET BERDASAR BLOSUM 80 UNTUK DATASET TANPA HDS 174
LAMPIRAN F. HASIL PENGUJIAN MENGGUNAKAN TOOLINFERENSI FILOGENETIK PHYLIP PROTPARS DENGAN AUGMENTED SET TIDAK BERDASAR BLOSUM 80 UNTUK DATASET DENGAN HDS 176
LAMPIRAN G. HASIL PENGUJIAN MENGGUNAKAN TOOL INFERENSI FILOGENETIK PHYLIP PROTPARS DENGAN AUGMENTED SETBERDASAR BLOSUM 80 UNTUK DATASET TANPA HDS 178