Multiple sequence aligment menggunakan hidden Markov model dengan augemented set dan pengaruhnya terhadap akurasi pohon filogenetik

AFIAHAYATI, Dra. Sri Hartati, M.Sc., Ph.D

2010 | Tesis | S2 Ilmu Komputer

Task dasar dalam menganalisa data biologi molekuler diantaranya adalah multiple 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 sequence dengan similarity yang rendah, metode ini akan menghasilkan MSA yang kurang optimal .Dalam tesis ini, dilakukan penelitian terhadap alternatif yang dapat dilakukan dalam melakukan multiple alignment terhadap sequence protein dengan similarity yang rendah menggunakan HMM, sehingga hasil MSA dapat dijadikan input dan menghasilkan pohon filogenetik yang lebih akurat. Alternatif yang dilakukan adalah membangun augmented set dengan parameter berupa jumlah child sequence dan prosentase mutasi yang dilakukan terhadap child sequence. Dilakukan dua jenis proses mutasi yaitu mutasi berdasar substituion matrix BLOSUM 80 dan mutasi secara random. Augmented set dijadikan input ke dalam HMM untuk mendapatkan MSA. Untuk mengestimasi parameter-parameter dalam HMM, digunakan algoritma pembelajaran Baum-Welch sedangkan untuk melakukan alignment dari unaligned sequence, digunakan algoritma Viterbi.Prototype tool dibangun menggunakan bahasa pemrograman Java dan memanfaatkan library Biojava.Akurasi pohon filogenetik yang menggunakan MSA dengan augmented set dibandingkan dengan MSA tanpa augmented set. Terdapat dua metode inferensi pohon filogenetik yang digunakan dalam penelitian ini, pertama adalah neighbour joining dengan tool ClustalX , kedua metode parsimony dengan tool Phylip Protpars. Data yang digunakan adalah data sequence asam amino ribosom 16S dari mitokondria. Hasil pengujian menunjukkan bahwa akurasi pohon filogenetik meningkat dengan menggunakan augmented set berdasar matrix BLOSUM 80 dan metode neighbour joining yang memiliki kriteria jumlah sequence dan HDS yang sedikit, serta selisih panjang maksimal dan panjang rata – rata sequence-nya rendah. Sedangkan akurasi pohon filogenetik menggunakan augmented set dan metode parsimony meningkat atau menurun.

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.

Kata Kunci : MSA,Pohon Filogenetik,HMM,Augmented Set,Sequence Ribosom 16S