MULTIPLE SEQUENCE ALIGNMENT MENGGUNAKAN HIDDEN MARKOV MODEL

Afiahayati Afiahayati, Sri Mulyana

Abstract


Mudah dan murahnya proses pengumpulan data biologi molekuler saat ini menyebabkan ukuran basis data genetika meningkat dengan pesat. Hal ini meningkatkan kebutuhan akan alat bantu komputasi untuk menganalisa data tersebut. Salah satu task dasar dalam menganalisa data biologi molekuler adalah Multiple Sequence Alignment. Program Multiple Sequence Alignment yang sering digunakan oleh praktisi biomolekuler adalah ClustalX yang menggunakan metode komputasi progressive pairwise alignment.

Salah satu metode yang saat ini banyak dikaji untuk menghasilkan Multiple Sequence Alignment adalah Hidden Markov Model. Hidden Markov Model cocok digunakan dalam Multiple Sequence Alignment karena Multiple Sequence Alignment dapat dipandang sebagai masalah pengenalan pola.  Hidden Markov Model menggunakan algoritma pembelajaran Baum-Welch untuk mengestimasi parameter-parameter dalam HMM dan algoritma Viterbi untuk melakukan alignment dari unaligned sequence.      

Pada penelitian ini dilakukan eksperimen untuk menerapkan Hidden Markov Model  dalam menghasilkan Multiple Sequence Alignment dari sequence protein yang belum ter-align dan dilakukan pengujian menggunakan data sequence protein BaliBASE 3.0 dengan membandingkan hasil alignment yang menerapkan Hidden Markov Model dengan hasil alignment program ClustalX. Hasil eksperimen menunjukkan bahwa implementasi Hidden Markov Model  pada Multiple Sequence Alignment  memiliki performa lebih baik pada data sequence yang memiliki identity tinggi dan mengalami penurunan perfoma pada data sequence yang panjang dan data sequence yang memiliki banyak noise seperti N/C terminal extension atau insertion.

References


Birney, E., 2001, Hidden Markov Models in Biological Sequence Analysis, Volume 45, IBM Journal of Research and Development.

Booch,G., Rumbaugh,J., Jacobson,I., 2005, The Unified Modeling Language User Guide. Addison Wesley Professional.

Colton, S., 2007, Introduction to Bioinformatics, Genetics Background, Course 3 41 Lecture Slide. Department of Computing Imperial College, London.

Gupta, S., 2004, Hardware Acceleration of Hidden Markov Models for Bioinformatics Applications, Boise State University.

Hughey, R., Krogh, A. , 1996, Hidden Markov Models for Sequence Analysis : Extension and Analysis of The Basic Method, University of California, Santa Cruz.

Koski, T., 2001, Hidden Markov Models for Bioinformatics, Kluwer Academic Publishers,Netherlands.

Krogh, A., Brown, M., Mian, I.S., Sjölander, K., Haussler, D., 1992, Hidden Markov Models in Computational Biology : Application to Protein Modeling, University of California, Santa Cruz.

Rabiner, L.R., 1989, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, Vol. 77, No. 2, pp. 257-286.

Schmidt,J.W., Matthes,F.,Niederée,C., 1999, Object-Oriented Analysis and Design Course Lecture Slide, TU Hamburg, Harburg.

Thompson, J.D., Frederic, P., Olivier, P., 1999, A Comprehensive Comparison of Multiple Sequence Alignment Programs, Nucleic Acid Research, Vol. 27, No. 13

Xiong, J., 2006. Essential Bioinformatics., Cambridge University Press, Cambridge.


Refbacks

  • There are currently no refbacks.