KAJIAN KOMPUTASI PARALEL PADA ALGORITMA TREE BASED OF CONSISTENCY OBJECTIVE FUNCTION FOR EVALUATION ALIGNMENT

KAJIAN KOMPUTASI PARALEL PADA ALGORITMA TREE BASED OF CONSISTENCY OBJECTIVE FUNCTION FOR EVALUATION ALIGNMENT (T-COFFEE) DALAM MASALAH MULTIPLE SEQUENCE ALIGNMENT

Muhammad Fauzan1, Gatot Fatwanto Hertono2 1 2

Departemen Matematika, FMIPA UI, Kampus UI Depok 16424

Departemen Matematika, FMIPA UI, Kampus UI Depok, 16424 1

[email protected], [email protected]

ABSTRAK Tree Based Of Consistency Objective Function For Evaluation Alignment (T-COFFEE) merupakan algoritma untuk menyelesaikan permasalahan multiple sequence alignment (MSA). Algoritma ini menggabungkan dua teknik, pertama Tree Based yang merupakan Progressive Alignment dan kedua Consistency Objective Function berupa extending library. Pada pembahasan tulisan ini akan digunakan data sequence dari database ensembl yang terdiri dari database DNA atau protein yang akan diproses dengan global alignment (Needleman-Wunsch) dan local alignment (Smith- Waterman) dengan harapan informasi yang dihasilkan pada akhir pensejajaran akan menggambarkan hasil penyejajaran yang optimal. Proses pembentukan primary dan extended library pada T-COFFEE membutuhkan waktu lama sehingga untuk mempercepat waktu proses T-COFFEE digunakan teknik komputasi paralel Graphic Processing Unit (GPU). Tulisan ini akan menjelaskan algoritma T-COFFEE, algoritma paralel T-COFFEE, serta mengukur efisiensi dari kedua algoritma tersebut.

ABSTRACT Tree Based Of Consistency Objective Function For Evaluation Alignment (T-COFFEE) is an algorithm to solve the problem of multiple sequence alignment (MSA). This algorithm combines two techniques, first is TreeBased with Progressive Alignment and second is Consistency of Objective Function by extending library. In this skripsi, we use the data from the ensembl database that consisting of DNA or protein data. Those data will be processed by the global alignment (Needleman-Wunsch) and local alignment (Smith-Waterman) that is expected to give optimal alignment result at the end of the alignment process. The generating of Primary and Extended Library is the most time consuming, hence to speed up the T-COFFEE process, a parallel version of T-COFFEE algorithm is needed by implementing parallel computing on Graphic Processing Unit (GPU). In this skripsi, the T-COFFEE algorithm, the parallel T-COFFEE algorithm, and the measurement of their speed up and efficiency will be discuss.

Keywords

: T-COFFEE, Primary Library, Exttended Library,

Parallel T-COFFEE

5 Universitas Indonesia

Kajian komputasi..., Muhammad Fauzan, FMIPA UI, 2013

Pendahuluan Bioinformatik adalah salah satu ilmu yang mempelajari bidang pengetahuan yang mencakup ilmu matematika, komputer, dan biologi, serta terkait dengan ilmu statistik, dan biokimia [1] Salah satu pembahasan yang penting dalam bioinformatika adalah permasalahan multiple sequence alignment (MSA) [1]. MSA memerlukan teknik-teknik penyejajaran barisan untuk mengolah basis data DNA dan protein. Dalam bioinformatika, proses MSA merupakan proses untuk mencari kemiripan antar semua barisan pada suatu basis data barisan DNA atau protein. Penyejajaran barisan DNA atau protein merupakan proses pengaturan barisan-barisan DNA atau protein sehingga dapat terlihat kesamaan pada dua atau lebih barisan tersebut [1]. Informasi tersebut dapat digunakan untuk penelitian lebih lanjut, misalnya mengidentifikasi hubungan evolusi pada suatu spesies. Kemiripan dua barisan DNA atau protein dapat diidentifikasi melalui skor kemiripan yang didapat dari penyejajaran barisan [1]. Pesatnya peningkatan banyak barisan dalam database DNA atau protein menjadi salah satu tantangan dalam proses penyejajaran di masa yang akan datang sehingga dibutuhkan langkahlangkah yang lebih efisien untuk menyelesaikan permasalahan ini. Salah satu algoritma MSA yang telah digunakan adalah algoritma T-COFFEE (Tree based Consistance of Objective Function For Evaluation alignmEnt). Dibandingkan dengan algoritma ClustalW, MUSCLE, ProbCons, dan FSA, algoritma ini memberikan jaminan hasil yang akurat namun membutuhkan waktu yang lebih lama dalam prosesnya sebagai contoh data yang besar seperti database DNA atau Protein [7]. Hal ini menimbulkan ide untuk mempercepat proses komputasinya melalui komputasi paralel GPU. TINJAUAN TEORITIS Pada bagian ini akan dibahas dasar-dasar teori terkait biologi molekuler, sequence alignment, progressive alignment, dan komputasi paralel yang akan digunakan pada bab-bab selanjutnya. Biologi Molekuler merupakan ilmu yang mempelajari fungsi dan jasad hidup atau organisme ditinjau dari struktur dan komponen penyusunnya[11] serta mengkajinya dalam skala molekul. Sebagai contoh pada interaksi dan pengaturannya pada berbagai sistem dalam sel, termasuk DNA (deoxyiribonucleic acid), RNA (ribonucleic acid), dan sintesis protein [10].


Dynamic Programming merupakan sebuah algoritma pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan Dalam menyelesaikan permasalahan dengan dynamic programming, dapat digunakan 2 pendekatan berbeda yaitu 1.

Maju (forward atau up-down) : bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, .., n. Urutan variabel keputusan adalah x1, x2, ..., xn

2.

Mundur(backward atau bottom-up) : bergerak mulai dari tahap n, mundur ke tahap n-1,n2,..,2,1. Urutan variabel keputusan adalah xn ,xn-1 ,…, x2, x1.

Contoh berikut adalah permasalahan penyejajaran barisan, nilai D menjadi cost yang harus dicari solusi optimum lokal maupun globalnya. Misalnya, diketahui 2 buah yaitu barisan W dan barisan V, di mana W=W1...Wi merupakan barisan yang akan disejajarkan, dan V =V1...Vj merupakan barisan yang akan dihitung nilai kesejajarannya terhadap barisan W, maka persamaan umum rekursif dari permasalahan menggunakan algoritma Dynamic Programming prinsip pendekatan maju (forward atau up-down) dapat dibentuk sebagai berikut :

⎧basis D(0, 0) = 0 ⎪ ⎧ D(i − 1, j − 1) + P(i, j ) ⎪ D(i, j ) = ⎨ ⎪ ⎪rekurens : min ⎨ D(i, j − 1) + δ (i, j ) + P(i, j ) ⎪ D(i − 1, j ) + δ (i, j ) + P(i, j ) ⎪ ⎩ ⎩

(1)

Keterangan : •

P(i, j) :mismatch penalty

⎧⎪0, jika Wi = V j P(i, j ) = ⎨ ⎪⎩1, jika Wi ≠ V j

δ(i, j) :gap penalty

⎧0, jika tidak ada residu ' ' ⎩1, jika ada residu '-'

δ (i, j ) = ⎨

Block Subtitution Matrix (BLOSUM) pertama kali diperkenalkan oleh Steven Henikoff dan Jorja G. Henikoff pada tahun 1992. Gagasan mereka adalah mendapatkan skor yang lebih baik dari dua protein yang berbeda untuk hasil penyejajaran protein yang lebih mirip. Mereka menggunakan database BLOK untuk mencari perbedaan barisan-barisan antar daerah yang conserved dari family protein. Oleh karena itu istilah BLOSUM berasal dari BLOcks


SUbstitution Matriks [4]. Suatu Matriks yang termasuk kelompok BLOSUM dinotasikan dengan BLOSUMr, dimana 0 < ! < 100. Tabel 1 Matriks BLOSUM 62 A

R

A

4

-1

R

-1

N

N

D

C

Q

E

G

H

I

L

K

M

F

P

S

T

W

Y

V

-2

-2

0

-1

-1

0

-2

-1

-1

-1

-1

-2

-1

1

0

-3

-2

0

5

0

-2

-3

1

0

-2

0

-3

-2

2

-1

-3

-2

-1

-1

-3

-2

-3

-2

0

6

1

-3

0

0

0

1

-3

-3

0

-2

-3

-2

1

0

-4

-2

-3

D

-2

-2

1

6

-3

0

2

-1

-1

-3

-4

-1

-3

-3

-1

0

-1

-4

-3

-3

C

0

-3

-3

-3

9

-3

-4

-3

-3

-1

-1

-3

-1

-2

-3

-1

-1

-2

-2

-1

Q

-1

1

0

0

-3

5

2

-2

0

-3

-2

1

0

-3

-1

0

-1

-2

-1

-2

E

-1

0

0

2

-4

2

5

-2

0

-3

-3

1

-2

-3

-1

0

-1

-3

-2

-2

G

0

-2

0

-1

-3

-2

-2

6

-2

-4

-4

-2

-3

-3

-2

0

-2

-2

-3

-3

H

-2

0

1

-1

-3

0

0

-2

8

-3

-3

-1

-2

-1

-2

-1

-2

-2

2

-3

I

-1

-3

-3

-3

-1

-3

-3

-4

-3

4

2

-3

1

0

-3

-2

-1

-3

-1

3

L

-1

-2

-3

-4

-1

-2

-3

-4

-3

2

4

-2

2

0

-3

-2

-1

-2

-1

1

K

-1

2

0

-1

-3

1

1

-2

-1

-3

-2

5

-1

-3

-1

0

-1

-3

-2

-2

M

-1

-1

-2

-3

-1

0

-2

-3

-2

1

2

-1

5

0

-2

-1

-1

-1

-1

1

F

-2

-3

-3

-3

-2

-3

-3

-3

-1

0

0

-3

0

6

-4

-2

-2

1

3

-1

P

-1

-2

-2

-1

-3

-1

-1

-2

-2

-3

-3

-1

-2

-4

7

-1

-1

-4

-3

-2

S

1

-1

1

0

-1

0

0

0

-1

-2

-2

0

-1

-2

-1

4

1

-3

-2

-2

T

0

-1

0

-1

-1

-1

-1

-2

-2

-1

-1

-1

-1

-2

-1

1

5

-2

-2

0

W

-3

-3

-4

-4

-2

-2

-3

-2

-2

-3

-2

-3

-1

1

-4

-3

-2

11

2

-3

Y

-2

-2

-2

-3

-2

-1

-2

-3

2

-1

-1

-2

-1

3

-3

-2

-2

2

7

-1

V

0

-3

-3

-3

-1

-2

-2

-3

-3

3

1

-2

1

-1

-2

-2

0

-3

-1

4

Progressive Alignment merupakan pendekatan yang paling banyak digunakan untuk masalah multiple sequence alignment, yang membangun sebuah MSA dengan menggabungkan pairwise dimulai dengan pasangan yang paling mirip sampai yang hanya memiliki sedikit kemiripan. Metode progressive alignment terdiri dari dua tahap : tahap pertama hubungan antara barisan direpresentasikan sebagai tree, yang disebut tree-guide, dan langkah kedua membangun MSA dengan cara menambahkan barisan sesuai dengan kedekatan pada tree guide [9]. Komputasi Paralel adalah teknik komputasi yang memanfaatkan beberapa komputer atau prosesor pada suatu waktu tertentu secara bersamaan. Komputasi paralel memiliki efisiensi yang besar/baik saat kapasitas data yang diproses sangat besar atau algoritma yang digunakan sangat kompleks dan memiliki proses komputasi yang banyak. Hal tersebut berdampak signifikan pada lamanya waktu komputasi yang diperlukan jika dijalankan secara sekuensial,


dengan komputasi paralel diharapkan waktu komputasi dapat lebih cepat. Untuk lebih jelas mengenai perbedaan komputasi sekuensial dan komputasi paralel, perhatikan Tabel 2. Tabel 2 Perbandingan Komputasi Sekuensial dengan Komputasi Paralel No

Komputasi Sekuensial

Komputasi Paralel

1

Program berjalan pada satu prosesor

Program berjalan pada dua atau lebih prosesor

2

Program diproses secara sekuensial

Program didekomposisi menjadi beberapa sub program yang dapat diproses secara paralel

3

Hanya satu instruksi yang bisa

Masing-masing sub program dieksekusi secara

dieksekusi pada waktu tertentu

bersamaan pada prosesor yang tersedia Setiap prosesor memiliki sub program yang sama atau data yang diproses sama

GPU Computing, saat ini perkembangan kartu grafis atau lebih dikenal sebagai GPU (Graphic Processing Unit) dengan teknologi manycore. GPU dikembangkan dalam sebuah platform yang dapat digunakan untuk memaksimalkan bukan hanya dari sisi graphics processing, namun juga untuk kepentingan komputasi pada umumnya. Platform ini dikenal dengan istilah GPGPU (General Purpose Computation on GPU). Cuda adalah salah satu bahasa pemrograman yang bekerja dengan memanfaatkan GPU. Bahasa ini merupakan ekstensi minimal dari bahasa pemrograman C dan C++. Cuda menyediakan tiga abstraksi utama, yaitu hierarki yang terdiri dari thread, shared memory, dan barrier synchronization. Tujuan dari pengembangan CUDA adalah untuk menuntun programmer membagi masalah ke dalam submasalah menjadi bagian-bagian yang lebih halus dan dapat diselesaikan secara independen atau paralel, kemudian membaginya menjadi bagian-bagian yang lebih halus dan dapat diselesaikan secara kooperatif dalam ranah paralelisme [6]. Untuk menerapkan model pemrograman CUDA, diperlukan sebuah arsitektur komputasi yang bisa menjadikan prosesor-prosesor pada GPU menjadi satu platform yang efisien untuk mengolah grafis dan aplikasi-aplikasi komputasi paralel yang lebih umum. METODE PENELITIAN Metode penelitian yang digunakan adalah studi literatur dan simulasi PEMAHASAN ALGORITMA Pada bab ini akan dibahas algoritma Tree based Consistency of Objective Function For Evaluation Alignment (T-COFFEE) untuk masalah multiple sequence alignment (MSA).


Multiple sequence alignment (MSA) adalah permasalahan dalam menyejajarkan 3 atau lebih barisan DNA atau Protein. Tujuan MSA sama dengan sequence alignment yaitu menyejajarkan barisan DNA atau Protein sehingga didapatkan gambaran hubuguan evolusi dari barisan-barisan tersebut [3]. Pada saat ini telah dikembangkan beberapa teknik penyejajaran, seperti ClustalW, MUSCLE, ProbCons, dan FSA namun pada tulisan ini hanya akan dibahas algoritma T-COFFEE. Tree Based of Objective Function For Evaluation Alignment (T-COFFEE) adalah salah satu metode penyelesaian MSA, algoritma ini menerapkan teknik tree based dan menggunakan objective function dalam mengolah database DNA/protein [3]. Secara garis besar tahapan dari algoritma T-COFFEE dapat disusun pada Gambar 1. Algoritma ini memberikan hasil yang akurat dengan proses yang lebih cepat. Input algoritma T-COFFEE merupakan database barisan protein atau DNA Sumber data algoritma T-COFFEE yaitu hasil penyejajaran global dan lokal barisan DNA atau protein [3]. Dalam mengolah input tersebut, untuk setiap pasang barisan, digunakan dua algoritma yaitu Needleman-Wunch (untuk global alignment) dan Smith Waterman (untuk local alignment). Proses penyejajaran global akan digunakan untuk memberikan satu kesejajaran full length antara setiap pasangan barisan, sedangkan pada penyejajaran lokal dihasilkan sepuluh penyejajaran lokal dengan skor terbaik, antara setiap pasangan barisan [3]. Sebagai ilustrasi dapat dilihat pada pada Gambar 1. Primary library berisi kumpulan pairwise alignment dari semua barisan yang telah disejajarkan. Pada tulisan ini digunakan struktur library seperti yang dijelaskan oleh Notredame [7]. Pada setiap library (lihat Gambar 3) disertakan informasi untuk masingmasing n(n-1)/2 pasang barisan, di mana n adalah banyak barisan. Berikut adalah penjelasan dari Gambar 3. Library memiliki n(n-1)/2 elemen, dimana elemen merupakan pasangan barisan yang disejajarkan. Sebuah elemen library tersusun dari beberapa entri, dan entri merupakan indeks dari pasangan berurutan dari residu yang bersesuaian (misalnya residu x barisan A sejajar dengan residu y barisan B) [3].


Sebagai akibat dari hal di atas, masing-masing pasangan merupakan sebuah konstrain, dimana tidak semua konstrain tersebut bernilai penting. Beberapa konstrain dapat berasal dari penyejajaran yang lebih baik. Hal ini digunakan untuk menghitung beberapa penyejajaran dan memberikan prioritas kepada pasangan residu yang berasal dari penyejajaran yang lebih baik [3]. Hal ini dicapai dengan menggunakan skema pembobotan [3].

Nedleeman-‐Wunsch (Global Pairwise Alignment)

Smith-‐Waterman (Local Pairwise Alignment)

Weighting Signal Addition

Primary Library Extension Extended Library

Progressive Alignment

Gambar 2 Tahapan Algoritma T-COFFEE (Notredame et al., 1998) Penentuan bobot primary library, T-COFFEE memberikan bobot untuk setiap pasangan residu sejajar di setiap library. Idealnya, sebuah pembobotan primary akan mencerminkan tingkat kebenaran dari sebuah konstrain. Bobot didapat dengan menghitung persentase dari residu pasangan barisan yang identik, dan hal ini menjadi indikator akurasi. Barisan dikatakan identik atau mirip ketika bobot pasangan barisan yang sejajar lebih dari 30% identitk [8]. Skema pembobotan ini terbukti sangat efektif untuk fungsi objektif dalam algoritma TCOFFEE [7]. Dalam hal ini Library akan berisi daftar bobot konstrain. Setiap konstrain memiliki bobot yang menunjukkan identitas persentase dari asal mula pasangan penyejajarannya [7]. Untuk setiap pasang barisan, primary library dihitung bersama dengan


bobot, menggunakan Needleman-Wunsch (untuk penyejajaran global) dan Smith-Waterman (untuk penyejajaran lokal).

Gambar 3 Struktur library [3] Kombinasi dari library adalah langkah menggabungkan dua atau lebih library yang telah dibangun. Tujuannya adalah untuk mendapatkan kombinasi yang efisien dari informasi penyejajaran lokal dan global. Hal ini diperoleh dengan cara menggabungkan global library dan local library melalui proses penjumlahan sederhana [7]. Jika setiap pasangan diduplikasi dari dua library, maka pasangan dari dua library digabungkan menjadi satu entri dan memiliki bobot sama dengan jumlah dari dua bobot. Dalam hal lain, entri baru akan dibangun untuk setiap pasangan yang ada. Pasang residu yang tidak cocok akan dianggap memiliki bobot nol. Lihat Gambar 4(c). Primary library ini dapat digunakan secara langsung untuk menghitung multiple sequence aligment. Proses MSA dapat menemukan penyejajaran yang terbaik dari bobot residu. Namun, untuk meningkatkan nilai informasi pada library diperlukan pemeriksaan konsistensi setiap pasangan residu dengan pasangan residu dari semua penyejajaran lainnya. Untuk setiap pasangan residu sejajar di library, kita dapat menetapkan bobot yang mencerminkan residu yang sejajar dan konsisten dengan residu dari semua barisan lainnya. Proses ini disebut extended library [3]. Extended library, tingkat akurasi MSA ditentukan oleh fungsi objektif yang digunakan. Dalam hal ini fungsi objektif juga digunakan pada tahapan extended library untuk menunjukkan kualitas hasil sequence alignment yang lebih akurat. Skor dari MSA


didefinisikan sebagai ukuran konsistensi pada library. Secara biologi, idealnya, semakin baik skor, semakin relevan penyejajaran. Permasalahan pencocokan satu set kendala terbobot menjadi MSA merupakan masalah NPcomplete. Sampai saat ini terdapat dua strategi optimasi yang digunakan [7], yang pertama dilakukan melalui genetic algorithm dan yang kedua menggunakan algoritma branch and bound. Hasil kedua metode tersebut masih dinilai kurang memuaskan. Salah satu alternatif untuk mengatasi masalah tersebut digunakan algoritma heuristik yang disebut extended library, dan didefinisikan sebagai formula berikut [8] :

EL( x, y,(i, j )) = PL( x, y,(i, j )) +

∑

∑

min{PL( x, z,(i, r )), PL( z, y,(r, j ))}

(2)

z∈{1,2,..., n} r∈{1,2,...,lz} z ≠ x, z ≠ y

Dimana PL adalah primary library, EL adalah extended library, x dan y elemen yang berhubungan, (i, j) titik dari entry yang dihitung, lz adalah panjang barisan z yang digunakan untuk memeriksa konsistensi dari bobot dan n adalah banyak barisan. Dengan pendekatan triplet, Extended library menggabungkan setiap pasangan residu dengan menyisipkan setiap satu barisan dari primary library selain pasangan yang sedang disejajarkan. Hal ini dilakukan agar bobot akhir menggambarkan kembali informasi yang terdapat dalam seluruh library. Sebagai contoh dapat dilihat pada Gambar 5 Hasil extended library akan diproses dengan teknik progressive alignment menggunakan algoritma neighbour-joining.


Gambar 4 (a) Progressive alignment, (b) Primary library, (c) Extended Library [3] Paralel T-COFFEE, Algoritma T-COFFEE membutuhkan waktu proses yang sangat lama, terutama pada saat pembentukan library. Algoritma ini memiliki kompleksitas mulai dari tahapan pembentukan primary library O(N2L2), extended library O(N3L2), Pembentukan phylogenetic tree O(N2L2) + O(N3), dan proses terakhir O(NL2). Waktu komputasi terbesar adalah pada saat proses pembentukan library [7], dan jika data yang diproses berukuran besar, maka pada tahapan pembentukan primary library dan extended library terdapat perhitungan yang sangat kompleks sehingga algoritma ini tidak efektif. Pada pembahasan selanjutnya akan dilakukan teknik paralel T-COFFEE. Tahapan Paralel Pairwise Alignment adalah langkah awal dari algoritma paralel TCOFFEE yaitu mengkalkulasikan penyejajaran global dan lokal. Untuk mendapatkan hasil pairwise alignment dengan akurasi yang tinggi, dibutuhkan metode yang tepat, seperti algoritma Needleman-Wunsch dan algoritma Smith-Waterman. Karena untuk data yang besar menyebabkan pengkalkulasian kompleks dan rumit, maka kedua algoritma tersebut diimplementasikan pada GPU. Algoritma paralel dari tahapan ini telah dibahas dalam jurnal lain [2]. Tahapan Paralel Primary Library merupakan langkah kedua dari algoritma paralel TCOFFEE yaitu membangun primary library (PL)). Informasi dari pairwise alignment digabungkan dan disusun dalam memori sehingga dapat digunakan seefisien mungkin (Gambar 6).


Gambar 5 Struktur dari Satu Library Entri [3] Karena seluruh PL membutuhkan banyak memori, maka diperlukan untuk membaginya ke bagian-bagian kecil, yang disebut partial primary libraries (PPLs), yang dapat diproses dengan satu GPU. Dengan kata lain, semua pekerjaan dapat dibagi menjadi subproblem, yang dinotasikan dengan window size [3]. Sehingga, yang harus dilakukan pada setiap subproblem yaitu menghitung sebanyak k+1 pairwise alignment untuk setiap pasang barisan yang direpresentasikan oleh window (Gambar 7). Banyaknya PPLs tergantung pada banyaknya input sequence n dan juga nilai parameter pada window size yang didapatkan dengan rumus

N PPL

n ⎡ ⎤ = ⎢ ⎢ window size ⎥⎥

2

(3)

Nilai dari NPPL mengindikasikan bahwa jumlah seluruh PL dapat dihitung secara independen. Setiap dua elemen pada library dibentuk dari setiap pasang barisan yang ada. Hal tersebut menghasilkan proses yang redundant. Untuk menghindari hal tersebut hanya diproses separuh dari pembentukan elemen library tersebut, sedangkan sisanya hanya diduplikasi. Data yang diduplikasi digunakan pada tahap pemebentukan EL pada GPU agar lebih efisien dan akan dipaparkan di pembahasan berikutnya [3]. Untuk menggunakan memori GPU secara efisien, struktur data khusus untuk PL telah dirancang melalui cara-cara berikut. Setiap elemen diinput sebagai entri one-dimensional array (Gambar 5). Satu entri memuat informasi tentang indeks dari dua residu yang sejajar serta bobot kesejajarannya.

Gambar 6 Transkipsi PPL ke PL [3]


Untuk meningkatkan efisiensi pada langkah extended library, semua entri diantara tiap elemen dirancang dengan menggunakan indeks yang mengacu ke barisan kedua. Maka, prosedur penggabungan pairwise alignment ke PPL, tahapannya juga dirancang dalam bentuk entri-entri.

Gambar 7 Tahap PL dan Langkah Paralel Pembentukan PL Metode ini dirancang dengan cara menggabungkan semua akses memori global dan menghilangkan problem pada shared memory. Dengan demikian, didapatkan prosedur yang sangat efisien dan waktu eksekusinya lebih singkat dibandingkan dengan waktu yang dibutuhkan untuk pairwise alignment. Untuk mendapatkan fleksibilitas dalam membagi kasus dari extended library ke subproblem yang sesuai, teknik penyimpanan PL dengan cara yang tepat adalah hal yang penting untuk diperhatikan. Proses mengcopy data ke memori global GPU merupakan langkah yang tidak optimal, oleh sebab itu, sebelum memulai proses extended library, dilakukan transkripsi semua PPLs membentuk satu PL(Gambar 6).


Tahapan Paralel Extended library, tujuan dari extended PL adalah untuk mengubah bobot dari library. Langkah algoritma ini membutuhkan waktu yang banyak dan terdapat beberapa extended yang kompleks. Proses dari progressive alignment membutuhkan satu elemen library untuk tiap pasang barisan. Jika terdapat n barisan berarti terdapat n x n perhitungan untuk membentuk extended library (EL). Setiap pasang barisan membentuk 2 elemen dari library tersebut. Oleh sebab itu untuk mengatasi masalah tersebut, data yang akan di-extended hanya elemen diagonal bawah dari PL [3]. Sama halnya dengan mengkontruksi PL, ketika membentuk extending library, banyak data yang diproses terlalu besar untuk dapat diselesaikan dalam satu langkah (sekuensial). Untuk mengatasi hal ini, seluruh kerja akan dibagi menjadi bagian yang lebih kecil sehingga dapat diselesaikan dengan satu GPU. Langkah ini akan lebih difokuskan untuk meminimalisasi transmisi data. Salah satu strategi yang dirancang adalah semua input PL dibagi dalam windows dengan size n x window size (catatan: windows dan windows size yang ini tidak berhubungan dengan yang sebelumnya) (Gambar 8).

Gambar 8 Alokasi PL di Memory untuk Pembentukan EL Sebuah task dihubungkan dengan tiap window untuk menghitung elemen yang terhubung dengan EL. Untuk mencegah pengcopy-an semua PL ke dalam graphics card dalam 1

n ⎡ ⎤ langkah (secara sequensial), setiap task dibagi ke 1, 2, … , ⎢ subtask, dan ⎢ window size ⎥⎥ tergantung pada seberapa banyak elemen diagonal bawah yang dapat dihitung. Setiap subtask membutuhkan 2 window dari PL yang disediakan dalam memori global, yaitu pasangan barisan utama (base window) dan barisan untuk menguji konsistensi (reinforcing window) (Gambar 8). Seperti yang disebutkan sebelumnya, untuk meningkatkan kualitas dari elemen (SEQx, SEQy) dari EL dengan menggunakan sebuah barisan SEQz, tiga elemen PL


dibutuhkan: (SEQx, SEQy), (SEQz, SEQy) dan (SEQz, SEQx). Untuk menyelesaikan proses extended library, beberapa windows harus ditransfer ke dalam memori: windows transfers =

w( w + 1) +w 2

(4)

n ⎡ ⎤ dimana w = ⎢ adalah banyaknya dari windows. ⎢ window size ⎥⎥ Untuk mencari semua PL dapat dicopy, nilai dari 4 harus dibagi dengan w: PL transfers =

( w + 1) +1 2

(5)

cost menyalin kembali hasil dari kartu grafis yaitu lebih kecil atau sama dengan : PL transfers =

( w + 1) 2w

(6)

Selanjutnya, transfer costs secara langsung bergantung pada window size yang sepenuhnya akan disesuaikan.

Gambar 9 Langkah-langkah Pengefektifan Memory Pada Proses Extended [3] Berikutnya akan dijelaskan tujuan dari menyimpan semua PL. Solusi paling tepat untuk mengatasi masalah pada kasus-kasus sebelumnya yaitu proses dilakukan dengan menyusun elemen dari seluruh PL berdasarkan indeks barisan kedua. Sehingga kedua windows yang diperlukan disimpan berdekatan dalam baris dari PL(seperti pada Gambar 9 bagian bawah kiri). Transfer dari memori global ke shared memory akan digabungkan dengan cara tersebut. Setiap subtask yang bersesuaian dengan grid yang dijalankan pada GPU tunggal dijalankan juga secara paralel. Dalam kasus ini, Grid terdiri dari windows size × blok windows size. Setiap blok meng-extend hanya satu elemen (Gambar 11). Misal, dalam satu blok ada 256 × 1


thread (Gambar 10). Sebuah thread tunggal meng-extend satu entri dari elemen yang berhubungan dengan semua barisan (Gambar 10). Dalam kasus ini diberikan elemen yang terdiri dari entri lebih dari 256, dan dipartisi kedalam 256 fragmen. Sebuah blok memproses fragmen satu demi satu: sebuah iterasi tunggal dari sebuah loop utama mengolah sebuah fragmen, frag x,y (dimana x dan y mengacu pada pasangan (SEQx,SEQy) yang di-extend) dan menyimpannya di shared memory (Gambar 10).

Block

Gambar 10 Langkah Paralel Pembentukan EL Pada poin ini, setiap bobot yang baru dibuat dari entri EL diinisialisasi dengan bobot PL yang berhubungan. Sebuah loop bersarang (nested loop) mengolah n - 2 barisan (z = 1, ... , n) ∧ (z ≠ x ) ∧ (z ≠ y). Loop tersebut menunjukkan pasangan operasi elemen ((SEQz, SEQy) dan (SEQz, SEQx)) yang dibutuhkan dalam proses extending. Elemen-elemen ini juga terfragmentasi (frag z,y, frag z,x) sesuai kebutuhan dan buffer dalam shared memory. Ketika satu entri frag x,y diproses oleh satu thread, frag z,y dan frag z,x juga diproses oleh setiap thread yang lain. Sebuah operasi inti kernel dari thread tunggal adalah untuk memeriksa keberadaan tuple berikut: ((a, b) x, y, (c, d) z, y, (e, f) z, x) sehingga b = d dan a = f, di mana (a, b) x, y menunjukkan sepasang indeks residu (a, b) unsur (SEQx, SEQy). Hal ini dicapai dengan cara berikut: sebuah thread melakukan scan ke buffer terkait dengan frag z,y dalam mencari indeks residu b pada posisi indeks kedua. Dalam hal ini, karena adanya frag z tersebut, maka y diurutkan berdasarkan indeks residu SEQy.


Waktu yang diperlukan pada tahap ini lebih singkat dari pada waktu yang dibutuhkan untuk membangun separuh PL sisanya. Selain itu, karena semua thread diberikan dalam warp untuk membaca shared buffer frag z, y dan frag z, x secara serentak, maka akan didapatkan percepatan waktu proses. Selain itu, setiap thread hanya memodifikasi bobot EL-nya sendiri yang terkait dengan (SEQx, SEQy). Pada akhir loop utama, iterasi seluruh blok menyimpan hasilnya ke memori global

Elemen 1,1

Elemen 1,2

Elemen 1,n

Elemen 2,1

Elemen n,n

Gambar 11 Proses Paralel pada EL IMPLEMENTASI PROGRAM Bagian ini akan membahas implementasi dan simulasi dari algoritma T-COFFEE serta mengukur speedup dan efisiensi dari algoritma paralelnya. Program ini dijalankan pada komputer dengan spesifikasi sebagai berikut : Prosesor

: Intel® Dual CoreTM E5500 @ 2.8GHz

GPU

: NVIDIA GeForce GTX 460, RAM 2 GB, 336 Core

Compiler

: NVIDIA CUDA Compiler (NVCC) v4.0.

Database Ensembl [12] menyediakan database barisan DNA dan protein. File database dalam format FASTA tersedia dari direktori yang sesuai 'fasta' di situs ftp.ensembl.org. Dokumen ini menjelaskan konvensi penamaan saat ini dan format batas header urutan yang digunakan oleh Ensembl. Deskripsi serupa juga tersedia dari file README pada direktori situs FTP. Sementara Ensembl juga menyediakan deskripsi yang lebih umum dari struktur situs FTP.


Implementasi algoritma T-COFFEE tersebut dalam progam menggunakan C++. Input dari program ini adalah database protein diambil dari database ensembl. Gambar 14 merupakan simulasi program dari database ensembl 3_664.fax sequence 115 s.d 134, dengan banyak barisan yang digunakan 20 barisan dan barisan terpanjang terdiri dari 108 karakter. Hasil yang diperoleh berupa database MSA yang sudah disejajarkan (Gambar 12), dengan waktu rata-rata yang dibutuhkan sekitar 29 detik. Running time untuk data dengan banyaknya 50 hingga 150 barisan dapat dilihat pada Tabel 3.

Gambar 12 Screenshot Output Hasil Penyejajaran Sekuensial T-COFFEE Tabel 3 Running time sekuensial T-COFFEE Banyak barisan

20

50

70

100

150

25

155

318

727

1602

Running Time

28

148

342

733

2331

(dalam detik)

27

160

349

746

1562

39

141

336

619

1692

26

142

339

684

1691

29

149.2

336.8

701.8

1175.6

Rata-rata(s)

Implementasi Algoritma T-COFFEE Paralel diimplementasikan dalam progam menggunakan CUDA.C. Input dari program ini adalah database Protein diambil dari database Ensembl. Gambar 13 merupakan screenshot output program dengan database barisan yang digunakan adalah database ensembl 3_664.fax sequence 115 - 214 dengan banyak barisan 100 dan barisan terpanjang terdiri dari 140 karakter. Hasil yang diperoleh berupa database MSA


Gambar 13 Screenshot Output program paralel T-COFFEE yang sudah disejajarkan, dengan waktu rata-rata yang dibutuhkan sekitar 23.14 detik. Running time untuk data sebanyak 20, 50, 70,150 barisan dengan 64, 128, 256 core dapat dilihat pada Tabel 4. Tabel 4 Running Time Paralel T-COFFEE dengan 64, 128, 256 Core Banyak barisan

20

50

70

100

150

Running Time

64

0.33

1.95

4.18

11.6

37.65

dengan banyak

128

0.34

2.31

5.63

16.91

56.65

prosesor- (detik)

256

0.45

3.16

7.68

23.14

78.83

Berdasarkan Tabel 10, running time paralel T-COFFEE dengan 64 core memberikan perhitungan yang lebih cepat dibandingkan dengan 128 atau 256 core. Perhitungan Speed-up dan Efisiensi, berdasarkan Tabel 10 algoritma T-COFFEE paralel memiliki running time lebih singkat dari pada running time algoritma sekuensialnya. Berdasarkan Tabel 10 diperoleh rata-rata speed-up sebesar 40.15 kali dan rata-rata efisiensi sebesar 0,15. hal ini menunjukkan bahwa algoritma paralel T-COFFEE memberikan percepatan hingga 40 kali dan effisiensi kinerja sebesar 15%.

Tabel 5 Speed-up dan Efisiensi Paralel T-COFFEE dengan 256 Core Banyak barisan

Running Time (detik)

Speed-up

Efisiensi

0.45

64.44

0.25

149.2

3.16

47.22

0.18

70

336.8

7.68

43.85

0.17

100

701.8

23.14

30.33

0.11

150

1175.6

78.83

14.91

0.06

40.15

0.15

Sequensial

Paralel

20

29

50

Rata-rata


Dari simulasi diatas tampak bahwa efisiensi algoritma paralel dengan 256 prosesor sangat kecil (15%). Selanjutnya akan dilakukan perbandingan speedup dan efisiensi antara 64, 128, dan 256 prosesor. Berdasarkan Tabel 6 dan 7, speedup dan efisiensi dari program paralel T-COFFEE menggunakan 64 prosesor lebih bagus daripada 128 dan 256 prosesor. Hal ini menunjukkan bahwa program paralel T-COFFEE dengan 64 prosesor memberikan hasil implementasi terbaik dengan rata-rata speedup 55.34 dengan efisiensi sebesar 0.86. Tabel 6 Speedup Paralel T-COFFEE dengan 64, 128, 256 Core Banyak barisan

20

50

70

100

150

Rata-rata Speed up

Speed up

64

63.11

61.07

60.82

60.5

31.22

55.34

dengan

128

85.29

64.59

59.82

41.5

20.75

54.39

256

64.44

47.22

43.85

30.33

14.91

banyak prosesor-

40.15

Tabel 7 Efisiensi Paralel T-COFFEE dengan 64, 128, 256 Core Banyak barisan

20

50

70

100

150

Rata-rata Efisiensi

Efisiensi

64

0.97

0.95

0.95

0.95

0.49

0.86

dengan

128

0.67

0.51

0.47

0.32

0.16

0.43

256

0.25

0.18

0.17

0.11

0.06

banyak prosesor-

0.15

Kesimpulan Algoritma T-COFFEE dapat menyelesaikan permasalahan multiple sequence alignment dan algoritma ini juga dapat dapat diterapkan dalam komputasi paralel berbasis sistem CUDA GPU. Algoritma T-COFFEE menggunakan konsep library yang membutuhkan waktu lama untuk membangun dan mengolah library, sehingga dengan algoritma paralel T-COFFEE serta langkah-langkah penentuan alokasi memori yang baik, maka waktu proses multiple alignment dapat dipercepat. Hasil implementasi algoritma paralel T-COFFEE pada bagian implementasi, terutama dengan menggunakan 64 prosesor pada GeForce GTX 460, menunjukkan bahwa speed-up rata-rata yang diberikan 55.34 kali lipat dan nilai efisiensi rata-rata sebesar 0.86. Hal ini menunjukkan


bahwa algoritma paralel T-COFFEE memberikan percepatan dan efisiensi yang sangat signifikan untuk penyelesaian MSA. DAFTAR PUSTAKA [1] Attwood, T.K., dan D.J. Parry-Smith. (1999). Introduction to Bioinformatics. Harlow. Pearson Education [2] Blazewicz, J., Formanowicz, P., Wojciechowski, P. (2011). Protein alignment algorithms with an efficient backtracking routine on multiple GPUs. BMC Bioinformatics 1471-2105. [3] Blazewicz, J. (2013). G-MSA — A GPU-Based, Fast and Accurate Algorithm for Multiple Sequence Alignment. J. Parallel Distrib. Comput. 73 32–41 [4] Henikoff, S., Henikoff, J.G.(1992). Amino Acid Substitution Matrices from Protein Blocks. PNAS 89 (22) 10915–10919. [5] Isaev, A. (2004). Introduction to Mathematical Methods in Bioinformatics. Springer, Canberra. [6] Lindholm, Erik, et al. (2008). Tesla: A Unified Graphics and Computing Architecture. IEEE Press. [7] Notredame, C., Higgins, D.G., Heringa, J. (2000). T-Coffee: A Novel Method for Multiple Sequence Alignments. Journal of Molecular Biology 302 (1) 205–217. [8] Sander, C., Schneider, R. (1991). Database of Homology-Derived Protein Structures and the Structural Meaning of Sequence Alignment. Proteins 9 (1) 56–68. [9] Tizag. (2008). PHP Tutorial.http://www.tizag.com, 2 Desember 2013,pk 15.52. [10] Witarto, A. B., & Sajidan. (2010). Bioinformatika: Trend dan Prospek dalam Pengembangan Keilmuan Biologi. Makalah dipresentasikan pada Seminar Nasional Pendidikan Biologi FKIP UNS, Jawa Tengah, Indonesia. [11] Yuwono, T. (2007). Biologi Molekular. Jakarta: Erlangga. [12] Ensembl databases—release 55 ftp://ftp.ensembl.org/pub/release-55, 2010


KAJIAN KOMPUTASI PARALEL PADA ALGORITMA TREE BASED OF CONSISTENCY OBJECTIVE FUNCTION FOR EVALUATION ALIGNMENT

Recommend Documents