Paralelisasi Algoritme Pairwise Alignment dan Neighbor Joining pada Progressive Multiple Sequence Alignment
View/ Open
Date
2017Author
Utomo, Agung Widyo
Kusuma, Wisnu Ananta
Wahjuni, Sri
Metadata
Show full item recordAbstract
Multiple sequence alignment (MSA) adalah permasalahan dasar dalam
Bioinformatika yang bertujuan menjajarkan lebih dari dua sekuens biologi untuk
menemukan kemiripan pada masing-masing sekuens. MSA digunakan dalam
analisis phylogenetic, identifikasi motif pada keluarga protein dan pemodelan
homologi tiga dimensi.
Tantangan yang dihadapi dalam melakukan implementasi MSA adalah
kompleksitas algoritme dan ukuran data sekuens yang besar. Progressive MSA
ClustalW merupakan metode heuristic yang banyak digunakan untuk
menyelesaikan masalah kompleksitas algoritme MSA. Beberapa penelitian
membuktikan bahwa paralelisasi progressive MSA dapat meningkatkan kinerja
dalam menghadapi ukuran data sekuens yang besar.
Penelitian ini bertujuan melakukan paralelisasi algoritme pairwise
alignment dan neighbor joining pada progressive MSA ClustalW menggunakan
model pemrograman message passing, shared memory, dan gabungan keduanya.
Perancangan program paralel dilakukan dengan empat tahap yaitu partitioning,
communication, agglomeration dan mapping. Perancangan program paralel
tersebut menghasilkan lima skenario implementasi untuk algoritme pairwise
alignment dan satu skenario untuk algortime neighbor joining. Skenario tersebut
antara lain pureMPI, pureOpenMP, ompInner, mpiOmpInner, dan mpiOmpOuter
pada algoritme pairwise alignment serta skenario pureOpenMP pada algoritme
neighbor joining.
Skenario pureOpenMP menjadi skenario terbaik pada algoritme pairwise
alignment dengan speedup hingga 12.20 kali menggunakan 20 prosesor. Skenario
pureOpenMP pada algoritme neighbor joining menghasilkan speedup hingga 6.11
kali menggunakan 20 prosesor. Algoritme pairwise alignment dan neighbor
joining memperoleh speedup terbaik menggunakan skenario pureOpenMP yang
merupakan implementasi model pemrograman shared memory. Penggunaan
skenario tersebut pada gabungan kedua algoritme diperoleh speedup hingga 12
kali menggunakan 20 prosesor. Paralelisasi kedua algoritme tersebut
menggunakan skenario pureOpenMP berkontribusi untuk menjaga algoritme
gabungan tetap kokoh pada data yang memiliki sekuens yang panjang dan jumlah
sekuens yang banyak.