IDENTIFIKASI SUATU SEKUEN KONSENSUS PADA SEKUEN DNA MENGGUNAKAN PEMROGRAMAN LINIER SKRIPSI DIAN NURHAYATI

UNIVERSITAS INDONESIA

IDENTIFIKASI SUATU SEKUEN KONSENSUS PADA SEKUEN DNA MENGGUNAKAN PEMROGRAMAN LINIER

SKRIPSI

DIAN NURHAYATI 0806452154

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK 2012

Identifikasi suatu..., Dian Nurhayati, FMIPA UI, 2012

UNIVERSITAS INDONESIA

IDENTIFIKASI SUATU SEKUEN KONSENSUS PADA SEKUEN DNA MENGGUNAKAN PEMROGRAMAN LINIER

SKRIPSI Diajukan sebagai salah satu syarat untuk memperoleh gelar sarjana sains

DIAN NURHAYATI 0806452154

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK 2012


HALAMAN PERNYATAAN ORISINALITAS

Skripsi ini adalah hasil karya sendiri, dan semua sumber baik yang dikutip maupun dirujuk telah saya nyatakan dengan benar.

Nama NPM Tanda Tangan Tanggal

: Dian Nurhayati : 0806452154 : : 6 Juni 2012

iii


HALAMAN PENGESAHAN

Skripsi ini diajukan oleh Nama NPM Program Studi Judul Skripsi

: : : :

Dian Nurhayati 0806452154 Sarjana Matematika Identifikasi suatu Sekuen Konsensus Pada Sekuen DNA menggunakan Pemrograman Linier

Telah berhasil diertahankan di hadapan Dewan Penguji dan diterima sebagai bagian persyaratan yang diperlukan untuk memperoleh gelar Sarjana Sains pada Program Studi S1 Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia

DEWAN PENGUJI

Pembimbing

: Alhadi Bustamam, PhD

(

)

Penguji

: Dr. Sri Mardiyati, M.Kom

(

)

Penguji

: Dr. rer. nat. Hendri Murfi, M.Kom

(

)

Penguji

: Bevina D Handari, PhD

(

)

Ditetapkan di Tanggal

: Depok : 6 Juni 2012

iv Identifikasi suatu..., Dian Nurhayati, FMIPA UI, 2012

KATA PENGANTAR

Alhamdulillah, puji syukur penulis panjatkan kepada Allah SWT, karena atas semua rahmat dan karunia yang telah Dia berikan sehingga penulis dapat menyelesaikan tugas akhir ini. Penulis sadar bahwa penyelesaian tugas akhir ini tidak terlepas dari bantuan, bimbingan dan dukungan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terima kasih kepada pihak-pihak yang telah berjasa dalam penulisan tugas akhir ini maupun selama penulis kuliah. Ucapan terima kasih terhatur kepada:

(1)

Alhadi Bustamam, PhD., selaku pembimbing penulis yang telah meluangkan waktu, membimbing, memberi masukan serta memberikan bantuan kepada penulis dalam menyelesaikan skripsi ini.

(2)

Dra. Saskya Mary Soemartojo M.Si., selaku pembimbing akademis penulis selama menjalani masa kuliah.

(3)

Seluruh dosen pengajar Departemen Matematika FMIPA UI yang telah memberikan ilmu dan bimbingan dalam belajar.

(4)

Seluruh karyawan di Departemen Matematika FMIPA UI atas bantuan yang diberikan.

(5)

Bapak, ibu dan kakak-kakak penulis yang telah memberikan dukungan, doa serta bantuan kepada penulis.

(6)

S. W. Wulandari yang telah menemani masa-masa kuliah penulis selama 4 tahun.

(7)

Vika dan Icha yang sudah mendengarkan curhatan penulis dan maaf sering merepotkan.

(8)

Januarina yang telah menjadi teman dekat penulis di masa kuliah.

(9)

Teman-teman penulis di Departemen Matematika ankatan 2008 : Ade, Agnes, Maimun, Andy, Awe, Anisah, Puput, Arief, Arkies, Arman, Asri, Oline, Cindy, Citra, Danis, Dede, Dhea, Dheni, Agy, Eka, Emy, Dhila, Siwi, Ega, Hendry, Hindun, Dhewe, Nora, Janu, Qiqi, Luthfa, Adhi, Ifah, Maulia, Mayta, Mei, Nadia, Nita, Vika, Numa, Restie, Sita, Risya, Bowo, Ines, Tuti, Wulan, Ucil, Fani,

v Identifikasi suatu..., Dian Nurhayati, FMIPA UI, 2012

Icha, Uchida, Lian, Umbu, Yulial. Terima kasih atas kebersamaan yang telah terjalin. (10)

Teman-teman Matematika UI.

(11)

Kakak yang telah menjalani kebersamaan selama 1,5 tahun. Terima kasih atas semangat, doa dan dukungan yang diberikan. Semoga kebersamaan kita selalu terjaga.

Penulis juga ingin mengucapkan terimakasih kepada seluruh pihak yang tidak dapat disebutkan satu per satu, yang telah membantu dalam penyusunan skripsi ini. Akhir kata, penulis mohon maaf jika terdapat kesalahan atau kekurangan dalam skripsi ini. Penuis berharap semoga skripsi ini bermanfaat bagi pembaca.

Penulis

2012

vi Identifikasi suatu..., Dian Nurhayati, FMIPA UI, 2012

HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI TUGAS AKHIR UNTUK KEPENTINGAN AKADEMIS

Sebagai sivitas akademik Universitas Indonesia, saya yang bertanda tangan di bawah ini:

Nama NPM Program Studi Departemen Fakultas Jenis karya

: Dian Nurhayati : 0806452154 : S1 Matematika : Matematika : Matematika dan Ilmu Pengetahuan Alam : Skripsi

demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Indonesia Hak Bebas Royalti Noneksklusif (Non-exclusive Royalty Free Right) atas karya ilmiah saya yang berjudul : Identifikasi suatu Sekuen Konsensus pada Sekuen DNA menggunakan Pemrograman Linier beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti Noneksklusif ini Universitas Indonesia berhak menyimpan, mengalihmedia/format-kan, mengelola dalam bentuk pangkalan data (database), merawat, dan memublikasikan tugas akhir saya selama tetap mencantumkan nama saya sebagai penulis/pencipta dan sebagai pemilik Hak Cipta. Demikian pernyataan ini saya buat dengan sebenarnya.

Dibuat di : Depok Pada tanggal : 6 Juni 2012 Yang menyatakan

( Dian Nurhayati )

vii Identifikasi suatu..., Dian Nurhayati, FMIPA UI, 2012

ABSTRAK

Nama Program Studi Judul

: Dian Nurhayati : Matematika : Identifikasi suatu Sekuen Konsensus pada Sekuen DNA menggunakan Pemrograman Linier

Sekuen konsensus adalah subsekuen yang paling sering muncul pada sekuen DNA. Sekuen ini berguna untuk menentukan letak dari protein. Dalam mencari sekuen konsensus harus memperhatikan posisi tiap basa dari sekuen DNA. Terdapat pola tertentuk untuk mentukan sekuen ini. Pencarian sekuen konsensus pada umumnya dilakukan dengan cara menyejajarkan subsekuen DNA dan memberikan skor, sekuen yang memberikan skor maksimum akan dijadikan sekuen konsensus. Pencarian skor maksimum ini dapat dilakukan dengan pemrograman linier. Dalam skripsi ini akan dibahas pencarian sekuen konsensus dan posisinya pada sekuen DNA dengan mencari skor maksimum menggunakan metode pemrograman linier. Kata kunci xii + 50 halaman Daftar Pustaka

: sekuen, konsensus, pemrograman linier, skor : 7 gambar; 13 tabel : 10 (1981-2005)

viii

Universitas Indonesia


ABSTRACT

Name Study Program Title

: Dian Nurhayati : Mathematics : Identification of a Consensus Sequence on DNA Sequences using Linear Programming

Consensus sequence is the most frequent subsequences at DNA sequences. This sequence used to find binding site of protein. To searching consensus sequence it is important to consider location every nucleotides on DNA sequences. There is specific pattern to find this sequence. Searching consensus sequence commonly done by aligning DNA subsequences and giving score, a subsequence which give maximum score will be consensus sequence. Searching maximum score can use linear programming. In this paper will discuss how to find consensus sequence and its location on DNA sequence with searching maximum score using linear programming method. Keywords xii + 50 pages Bibliography

: sequences, consensus, linear programming, skor : 7 figures; 13 tables : 10 (1981-2005)

ix



DAFTAR ISI

HALAMAN PERNYATAAN ORISINALITAS ................................................... iii HALAMAN PENGESAHAN................................................................................ iv KATA PENGANTAR .............................................................................................v HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI ............................ vii ABSTRAK ........................................................................................................... viii ABSTRACT ........................................................................................................... ix DAFTAR ISI ............................................................................................................x DAFTAR GAMBAR ............................................................................................. xi DAFTAR TABEL .................................................................................................. xi DAFTAR LAMPIRAN ......................................................................................... xii 1. PENDAHULUAN ...............................................................................................1 1.1 Latar Belakang ...............................................................................................1 1.2 Perumusan Masalah dan Ruang Lingkup .......................................................2 1.3 Tujuan Penulisan ............................................................................................3 1.4 Jenis Penelitian dan Metode yang digunakan ................................................3 2. LANDASAN TEORI..........................................................................................4 2.1 Teori Dasar Genetika .....................................................................................4 2.2 Teori Dasar Pemodelan Matematis ................................................................7 2.3 Teori Dasar Pemrograman Linier...................................................................8 2.4 Metode Simpleks..........................................................................................11 2.5 Analisa Kompleksitas...................................................................................12 3. IDENTIFIKASI SEKUEN KONSENSUS PADA SEKUEN DNA MENGGUNAKAN PEMROGRAMAN LINIER.........................................14 3.1 Deskripsi Masalah ........................................................................................14 3.1 Formulasi Matematika .................................................................................15 3.3 Penyelesain Masalah ....................................................................................21 4. IMPLEMENTASI PROGRAM ......................................................................24 4.1 Simulasi Program .........................................................................................26 4.2 Analisa Kompleksitas...................................................................................27 5. PENUTUP .........................................................................................................31 5.1 Kesimpulan ..................................................................................................31 5.2 Saran.............................................................................................................31 DAFTAR PUSTAKA ...........................................................................................32 LAMPIRAN ..........................................................................................................33

x



xi

DAFTAR GAMBAR

Gambar 2.1 Heliks ganda dari sekuen DNA ............................................................5 Gambar 2.2 Skema dogma sentral ...........................................................................5 Gambar 2.3 Tabel simpleks....................................................................................13 Gambar 4.1 Tampilan masukkan dan keluaran untuk dua sekuen DNA ...............26 Gambar 4.2 Grafik waktu periterasi terhadap banyaknya iterasi ..........................27 Gambar 4.3 Tampilan masukkan dan keluaran untuk dua sekuen DNA E.Coli ....29 Gambar 4.4 Tampilan masukkan dan keluaran untuk tiga sekuen DNA E.Coli....29

DAFTAR TABEL

Tabel 3.1 Ringkasan nilai fungsi objektif dari tabel akhir simpleks ..................... 23 Tabel 4.1 Estimasi waktu running program .......................................................... 28 Tabel Lampiran 1.1 Tabel awal simpleks untuk , = 1 dan , = 1 ................ 33 Tabel Lampiran 1.2 Tabel kedua simpleks untuk , = 1 dan , = 1 .............. 34 Tabel Lampiran 1.3 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 35 Tabel Lampiran 1.4 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 36 Tabel Lampiran 1.5 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 37 Tabel Lampiran 1.6 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 38 Tabel Lampiran 1.7 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 39 Tabel Lampiran 1.8 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 40 Tabel Lampiran 1.9 Tabel akhir simpleks untuk , = 1 dan , = 1 ............... 41 Tabel Lampiran 1.10 Tabel akhir simpleks untuk , = 1 dan , = 1 ............. 42 Tabel Lampiran 1.11 Tabel akhir simpleks untuk . = 1 dan , = 1………..43



DAFTAR LAMPIRAN

Lampiran 1 Tabel simpleks ....................................................................................33 Lampiran 2 Daftar sekuen DNA E.Coli .................................................................44 Lampiran 3 Listing Program ..................................................................................46

xii



BAB 1 PENDAHULUAN

1.1 Latar Belakang

DNA (deoxyribonucleid acid) merupakan dasar hereditas yang disusun oleh empat nukleotida, yaitu adenin (A), guanin (G), sitosin (C) dan timin (T). Ketika keempat nukleotida tersebut tersusun menjadi polimier linier berdimensi satu, akan terbentuk sekuen DNA (Yi-Ping, 1998). Schneider (2002), menjelaskan bahwa dalam sekuen DNA terdapat sekuen dasar yang sering muncul di sekuen lainnya setelah sekuen-sekuen DNA itu disejajarkan. Sekuen dasar ini disebut sekuen konsensus. Sekuen konsensus ini dapat digunakan untuk menemukan binding site yang merupakan tempat melekatnya protein. Dalam aplikasinya, bnding site digunakan sebagai target aksi untuk meletakkan molekul baru pada perancangan obat (Yi-Ping, 1998). Salah satu kesulitan dalam mencari sekuen konsensus menurut Schneider (2002) adalah perbedaan sekuen konsensus pada setiap sekuen DNA. Setiap sekuen DNA akan mempunyai sekuen konsensusnya sendiri, akan tetapi sekuen konsensus yang diperoleh dari satu sekuen DNA mungkin saja berbeda dengan yang diperoleh di sekuen DNA lainnya. Misalkan pada tiga sekuen DNA, akan dicari sekuen konsensus terdiri dari enam basa. Ketiga sekuen konsensus yang diperoleh yaitu TATAAT, GATAAT dan TATAAT. Sekuen DNA pertama dan kedua mempunyai sekuen konsensus yang berbeda, sedangkan sekuen DNA pertama dan ketiga mempunyai sekuen konsensus yang sama. Sekuen konsensus yang akan kita cari adalah sekuen konsensus yang paling sering muncul. Untuk tiga sekuen DNA tersebut akan diperoleh sekuen konsensus TATAAT. Kesulitan lainnya dalam menemukan sekuen konsensus yaitu posisi sekuen konsensus pada setiap sekuen DNA berbeda (Schneider, 2002). Prinsip dasar untuk mencari sekuen konsensus adalah dengan menyejajarkan sekuen-sekuen DNA untuk dibandingkan dan dihitung skor kemiripannya. Ada beberapa metode yang pernah digunakan untuk mencari sekuen konsensus, diantaranya adalah metode Maximum Likelihood oleh Brazma

1



2

(1998) dan metode Pemrograman Nonlinier oleh Ecker (2002). Namun dua metode tersebut mempunyai kekurangan karena hanya menemukan nilai yang merupakan optimum lokal bukan optimum global (Han-Lin dan Chang-Jui, 2005). Sehingga dalam skripsi ini akan digunakan metode lain yang dapat menemukan nilai optimum global dari skor kemiripan tersebut. Salah satu metode yang dapat digunakan adalah dengan menggunakan pemrograman linier. Solusi optimal dari pemrograman linier ini akan menghasilkan nilai optimum global (Schrage, 1999). Pemrograman linier adalah suatu teknik matematika dalam memilih program terbaik dari sekumpulan daerah layak. Dalam pemrograman linier terdapat beberapa variabel yang di gunakan yaitu variabel terikat berupa fungsi tujuan, serta variabel bebas berupa variabel keputusan. Metode ini disebut linier karena hubungan antar variabelnya bersifat linier. Persoalan pemrograman linier adalah bagaimana mengoptimalkan (maksimum atau minimum) variabel terikat (fungsi tujuan dari variabel keputusan) terhadap kendala linier. Solusi optimal dari pemrograman linier adalah nilai-nilai dari variabel keputusan yang dapat dimasukkan ke dalam fungsi tujuan sedemikian sehingga fungsi tujuan akan menghasilkan nilai yang optimal (Wu dan Coppins, 1981). Dalam skripsi ini akan dilakukan identifikasi sekuen konsensus dari sekuen DNA menggunkan metode pemrograman linier.

1.2 Perumusan Masalah dan Ruang Lingkup

Bagaimanakah menemukan sekuen konsensus dan posisinya pada sekuen sekuen DNA yang telah diketahui menggunakan pemrograman linier. Permasalahan yang dibahas dalam skripsi ini hanya mencari sekuen konsensus dengan pola

, dimana

,

{ , , , } dan

adalah gen promotor, dengan = 1,2, … ,10. Serta minimal terdapat dua sekuen DNA yang telah diketahui.



3

1.3 Tujuan Penulisan

Dari rumusan masalah diatas tugas akhir ini bertujuan untuk menemukan sekuen konsensus dan posisinya pada sekuen DNA yang telah diketahui menggunakan pemrograman linier.

1.4 Jenis Penelitian dan Metode yang Digunakan

Penelitian ini dilakukan dengan menggunakan studi pustaka serta simulasi program.



BAB 2 LANDASAN TEORI

Pada bab ini akan dijelaskan teori-teori yang akan digunakan dalam bab selanjutnya. Teori-teori tersebut mencakup teori dasar genetika, pemodelan matematis, pemrograman linier, metode simpleks serta analisa kompleksitas.

2.1 Teori Dasar Genetika

DNA (deoxyribonucleid acid) merupakan sebuah polimer yang terbentuk dari molekul kecil yang disebut nukleotida dan berperan sebagai dasar hereditas. Informasi mengenai hereditas ini digambarkan dalam sekuen DNA mereka. Sekuen DNA adalah polimer linier berdimensi satu yang disusun oleh empat nukleotida berbeda, yaitu adenin (A) sitosin (C) guanin (G) dan Timin (T). Dengan kata lain sekuen DNA adalah sekuen yang disusun oleh 4 huruf A, C, T dan G, selanjutnya 4 huruf ini akan disebut sebagai basa nukleotida atau basa. Identifikasi sekuen DNA tersebut dapat memberikan informasi mengenai perbedaan spesies yang satu dengan yang lainnya, walaupun mereka mempunyai nukleotida yang sama. DNA organisme ditentukan dengan proses yang disebut sequencing. DNA sequencing meliputi proses penentuan empat basa nukleotida A, C, G dan T hingga membentuk sekuen DNA. Proses sequencing yang sering digunkan biasanya dilakukan dengan metode pemisahan fragmen DNA dengan gel electrophoresis (Yi-Ping, 1998). DNA terdapat di untai ganda dan setiap basa dalam 2 untai tersebut saling komplemen. Misalnya A berpasangan dengan T dan G berpasangan dengan C, mereka saling dipasangkan dengan ikatan hidrogen. Untai ganda ini berbentuk heliks, sehingga lebih dikenal dengan sebutan heliks ganda (double helix) (YiPing, 1998).

4



5

Gambar 2.1 Heliks ganda dari skuen DNA [Yi-Ping, 1998].

Informasi genetik yang dibutuhkan oleh organisme dibawa oleh DNA. Alur parjalanan informasi dimulai dari DNA sampai diterima oleh sel, diringkas dalam Dogma Sentral (Yi-Ping,1998). Dapat digambarkan dengan skema sebagai berikut:

Gambar 2.2 Skema dogma sentral.

Langkah awal dari DNA untuk sintesis protein disebut transkripsi. Transkripsi yaitu proses penyalinan informasi di DNA menjadi salinan yang disebut RNA. Jika bagian dari sekuen DNA yang disalin untuk dijadikan RNA berfungsi menerjemahkan protein, RNA yang terbentuk disebut messenger, atau mRNA. Selain itu juga terdapat transfer RNAs (tRNAs) dan ribosomal RNAs (rRNAs), yang dibutuhkan pada saat translasi. Dalam transkripsi, basa nukleotida DNA A, C, T, G berturut-turut dituliskan ke dalam basa nukleotida RNA menjadi A, C, U (urasil (U) menggantikan timin (T)) dan G. (Yi-Ping, 1998).



6

Transkripsi melalui 3 tahapan proses : (1) Inisiasi, dimulai dengan enzim yang disebut RNA polimerase menempel pada barisan di hulu (upstream) gen promotor. Gen promotor merupakan gen yang sering muncul pada sekuen DNA, tetapi gen promotor ini hanya mempunyai satu fungsi yaitu sebagai titik awal proses transkripsi; (2) Elongasi (pemanjangan), setelah promotor RNA polimerase melekat pada enzim tersebut akan terus bergerak sepanjang molekul DNA, mengurai dan meluruskan heliks tersebut; (3) Terminasi (Penghentian), dimana polimerase RNA mencapai barisan terminator di DNA dan kemudian transkripsi berhenti. Selama transkripsi, untaian heliks ganda DNA yang pertama berpisah dengan memutus ikatan hidrogen pasangan nukloetida. Salah satu untai dari DNA ini kemudian digunakan untuk menjadi template untai tungal RNA (Yi-Ping, 1998). Tahap akhir dalam skema Gambar 2.2 adalah translasi, yaitu proses penerjemahan RNA menjadi protein. Informasi yang telah diterjemahkan di mRNA digunakan untuk menyusun asam amino untuk membentuk protein. Protein merupakan komposisi dari 20 asam amino berbeda. Masing-masing asam amino ini diterjemahkan dari komposisi 3 nukleotida. Terdapat 4 basa nukleotida pada saat translasi (A, G, U dan C), sehingga terbentuk 4 = 64 kombinasi basa nukleotida untuk menghasilkan asam amino. Satu asam amino yang sama dapat diterjemahkan dari beberapa komposisi basa nukelotida yang berbeda, seperti asam amino Leucine (leu) dapat diterjemahkan dari 6 komposisi basa nukleotida yang berbeda. Selain itu terdapat 3 komposisi nukleotida UAA, UAG dan UGA yang tidak diterjemahkan menjadi asam amino, komposisi basa nukleotida ini berfungsi untuk menghentikan proses translasi. Dalam sekuen DNA juga terdapat sekuen dasar yang sering muncul di sekuen lainnya setelah sekuen-sekuen DNA itu disejajarkan. Sekuen dasar ini disebut sekuen konsensus. Sekuen konsensus ini dapat digunakan untuk menemukan binding site yang merupakan tempat melekatnya protein (Schneider, 2002). Binding site ini sebagai tempat faktor transkripsi, dimana faktor transkripsi merupakan elemen pengatur untuk melaksanakan transkripsi sampai terbentuknya protein. Salah satu kegunaan binding site adalah sebagai lokasi target aksi untuk penempatan molekul baru pada perancagan obat (Yi-Ping, 1998).



7

2.2 Teori Dasar Pemodelan Matematis

Model adalah suatu objek atau konsep yang digunakan untuk merepresentasikan sesuatu. Hal yang akan dimodelkan tersebut diubah ke dalam ukuran dan bentuk yang mudah dipahami. Model matematika adalah suatu model yang bagian-bagiannya menggunakan konsep matematika, seperti konstanta, variabel, fungsi, pertidaksamaan dan lain-lain (Meyer, 1985). Menurut Meyer (1985) model matematika tidak dapat dibentuk menggunakan alat atau program. Pembentukan model matematika ini dilakukan secara manual. Ada tiga tahapan yang dilalui untuk membentuk model matematika, yaitu : Formulasi, Manipulasi Matematika dan Evaluasi. 1. Formulasi •

Menentukan pertanyaan. Dalam persoalan yang akan di buat model matematikanya, pertanyaan di dalamnya biasanya masih kurang jelas, sehingga kita harus memperjelasnya, sedangkan jika dalam masalah tersebut pertanyaannya terlalu luas, yang harus dilakukan adalah membagi pertanyaan tersebut kedalam beberapa subbagian.

•

Tentukan faktor-faktor yang penting dalam masing-masing pertanyaan dan hubungannya.

•

Deskripsi matematika. Masing-masing perhitungan di representasikan ke dalam bentuk matematika yang cocok, contohnya variabel, fungsi, dan bentuk geometris. Masing-masing hubungan variabel atau hasil penghitungan dapat direpresentasikan menggunakan persamaan, pertidaksamaan atau asumsi matematika lainnya yang cocok.

2. Manipulasi Matematika Formulasi matematika jarang memberikan jawaban secara langsung. Perlu digunakan proses matematika untuk menyelesaikannya. Proses ini mengandung perhitungan, menyelesaikan persamaan, membuktikan teorema dan lain-lain. 3. Evaluasi Dalam memutuskan apakah suatu model baik atau tidak, ada banyak hal yang dapat kita hitung. Pertanyaan paling penting adalah apakah model



8

tersebut memberika jawaban yang baik atau tidak. Jika jawabannya tidak cukup akurat, atau model ini mempunyai kekurangan, kita harus berusaha mengidentifikasi kekurangannya. Mungkin kesalahan terjadi ketika manipulasi matematika, tetapi dalam kebanyakan kasus, yang dibutuhkan adalah formulasi baru. Sebagai contoh, terdapat beberapa perhitungan atau hubungan yang kita abaikan padahal sesungguhnya penting. Setelah terbentuk formulasi baru, kita akan melakukan manipulasi matematika baru dan evaluasi baru. Sehingga model matematika baru terbentuk.

2.3 Teori Dasar Pemrograman Linier

Pemrograman linier adalah suatu teknik matematika dalam memilih program terbaik dari sekumpulan daerah layak. Metode ini disebut linier karena hubungan antar variabelnya bersifat linier (Wu dan Coppins, 1981). ,

Definisi 2.1 (Winston, 1995). Fungsi

,…,

" adalah

$ , $ , … , $" ,

( ,

( ,

, ...,

" )dari

fungsi linier jika dan hanya jika untuk beberapa konstanta ,…,

")

=$

+ $

+ … + $"

".

Definisi 2.2 (Winston, 1995). Untuk fungsi linier ( ,

sebuah nilai ', maka pertidaksamaan ( ,

,…,

")

( ,

,…,

≥ ' adalah pertidaksamaan linier.

")

≤ ' dan

, ...,

")

dan

Menurut Winston (1995), dalam pemrograman linier ini terdapat : 1. Variabel keputusan yaitu variabel bersangkutan yang mendeskripsikan tujuan. 2. Fungsi objektif atau fungsi tujuan yaitu fungsi yang bertujuan untuk memaksimumkan atau meminimumkan. 3. Kendala yaitu syarat yang harus dipenuhi oleh variabel keputusan. Persoalan pemrograman linier adalah bagaimana mengoptimalkan (maksimum atau minimum) variabel terikat (fungsi linier dari variabel bebas) terhadap kendala linier. Solusi optimal dari pemrograman linier adalah nilai-nilai dari variabel keputusan yang dapat dimasukkan ke fungsi tujuan sehingga akan menghasilkan nilai yang optimal (Wu dan Coppins, 1981). Secara umum pemrograman linier dapat ditulis sebagai berikut :



9 =$

Optimasi

+$

.

Kendala

+.

.

+.

∑",- . , ,

,

,…,

"

+ ⋯+ .

+.

./

Atau

+ ⋯ + $"

+⋯+.

= ∑",- $,

" "

" "

+ ⋯ + ./"

≤ ', , "

≥0

≤'

,

≤'

"

≤ '/

= 1,2, … , 0

Dimana : ,

,…,

"

= variabel keputusan = fungsi tujuan

$ , $ , … , $"

= koefisien fungsi tujuan

'

= konstanta dari kendala ke-

. , . , … , . " = koefisien variabel keputusan pada kendala ke-

(Wu dan Coppins, 1981)

Solusi yang ditemukan dari bentuk model pemrograman linier adalah optimum global (Schrage, 1999). Suatu nilai

dikataka optimum lokal pada

( ) apabila ( ) ≥ ( ) ketika memaksimumkan dan ( ) ≤ ( ) ketika

meminimumkan, untuk nilai berpusat di

yang berada pada sebuah selang kecil yang

, sedangkan optimum global terjadi apabila pertidaksamaan tersebut

berlaku untuk semua nilai

(dalam domain yang didefinisikan ( )) (Wu dan

Coppins, 1981).

Teorema 2.1 (Bronson, 1988). Jika ( ) kontinu pada selang tertutup dan

terbatas [., '], maka ( ) memiliki optimum global (baik maksimum maupun minimum) pada selang ini.

Teorema 2.2 (Bronson, 1988). jika ( ) memiliki sebuah optimum lokal

di

dan jika ( ) dapat didefinisikan pada sebuah selang kecil yang berpusat di

, maka ’( ) = 0.

Teorema 2.3 (Bronson, 1988). jika ( ) dapat didefinisikan dan

diferensialkan dua kali pada sebuah selang kecil yang berpusat di

, dan jika

’( ) = 0 dan "( ) > 0, maka ( ) memiliki sebuah minimum lokal di

Sedangkan jika ’( ) = 0 dan ”( ) < 0, maka ( ) memiliki sebuah maksimum lokal di

.

. Universitas Indonesia


10

Contoh model pemrograman linier: Sebuah pabrik mebel yang memproduksi meja dan kursi, memerlukan dua jenis kayu yang dibutuhkan oleh masing-masing produk. Setiap meja memerlukan 5 m kayu jenis A dan 2 m kayu jenis B serta 4 jam waktu pengerjaannya. Sedangkan setiap kursi memerlukan 2 m kayu jenis A dan 3 m kayu jenis B serta 2 jam waktu pengerjaannya. Dalam penjualan produknya, pabrik ini akan memperoleh keuntungan Rp. 12.000 untuk setiap meja dan Rp. 8.000 untuk setiap kursi. Namun dalam seminggu hanya terdapat persediaan 150 m kayu jenis A dan 100 m kayu jenis B serta 80 jam pengerjaan. Pabrik ini ingin mengetahui berapa banyak produk yang harus diproduksi untuk memaksimumkan keuntungan. Variabel keputusan : Banyaknya meja yang diproduksi : Banyaknya kursi yang diproduksi

1. Fungsi objektif Pabrik ingin memaksimumkan keuntungan. Setiap penjualan meja memberikan keuntungan Rp. 12.000 sehingga total keuntungan yang diperoleh dari penjualan meja adalah 12.000 . Sedangkan setiap penjualan kursi akan memberikan keuntungan sebesar Rp. 8000, maka total keuntungan yang diperoleh dari penjualan kursi adalah 8.000 . Fungsi

merupakan fungsi objektif yang

ingin memaksimumkan total keuntungan yang diperoleh dari penjualan kedua produk tersebut, sehingga fungsi tersebut adalah : = 12000

+ 8000

2. Kendala Terdapat tiga kendala pada masalah ini. Persediaan kayu jenis A dalam seminggu sebanyak 150 m, untuk membuat meja dibutukan 5 m dan untuk membuat kursi diperlukan 2 m. sehingga kendala untuk kayu jenis A adalah: 5

+2

≤ 150

Persediaan kayu jenis B selama seminggu sebanyak 100 m. untuk membuat meja memerlukan 2 m kayu jenis B dan untuk pembuatan kursi memerlukan 3 m kayu jenis B. sehingga kendala untuk kayu jenis B adalah : 2

+3

≤ 100



11

Produksi meja dan kursi tersebut hanya dapat diakukan selama 80 jam dalam seminggu. Sedangkan untuk pembuatan meja memerlukan 4 jam pengerjaan serta untuk pembuatan kursi memerlukan 2 jam pengerjaan. Sehingga kendala untuk waktu pengerjaan adalah : 4

+2

≤ 80

Masing-masing variabel keputusan harus nonnegatif, kendalanya dapat ditulis sebagai berikut :

≥ 0 dan

≥0

Masalah pabrik mebel tersebut dapat diringkas menjadi: Memaksimumkan

= 12000

+ 8000

Dengan syarat 5

+2

≤ 150 kayu jenis A

4

+2

≤ 80 waktu pengerjaan

2

+3

,

≤ 100 kayu jenis B

≥ 0 nonnegativitas

Contoh diatas merupakan contoh pemodelan masalah menjadi pemrograman linier. Masalah pencarian sekuen konsensus juga dapat dimodelkan menjadi bentuk pemrograman linier yang akan dibahas dalam bab selanjutnya.

2.4 Metode Simpleks

Untuk menyelesaikan pemrograman linier dapat menggunakan salah satu metode yaitu metode simpleks. Metode simpleks dikembangkan oleh Prof. George B. Dantzig untuk menyelesaikan masalah pemrograman linier (Wu dan Coppins, 1981). Metode ini terdiri dari beberapa tahapan yaitu. Tahap 1 : Bentuk masalah pemrograman linier kedalam bentuk standar. Tahap 2 : Pilih 0 variabel (0 adalah banyaknya kendala) untuk

membentuk basis awal yang layak, variabel ini disebut variabel dasar. Semua variabel bukan dasar nilainya dibuat sama dengan nol. Tahap 3 : Evaluasi variabel bukan dasar untuk melihat variabel mana yang memperbaiki fungsi objektif. Jika tidak ada yang memperbaiki maka solusi sudah



12

optimal dan variabel yang terdapat dalam basis adalah variabel yang

memaksimalkan dengan nilai masing-masing variabel terdapat pada kolom ' . Jika ada yang memperbaiki maka variabel yang memberikan perbaikan terbesar per unit pada fungsi tujuan dipilih untuk masuk basis dan lanjutkan ke tahap 4. Tahap 4 : Pilih salah satu variabel dasar untuk meninggalkan basis, dengan tetap menjaga ketidaknegativan, kemudian lanjutkan ke tahap 5. Tahap 5 : Lakukan perubahan basis dengan pivoting. Variabel baru yang masuk kedalam basis telah dipilih pada tahap 3 sedangkan variabel yang keluar dari basis dipilih pada tahap 4. Kemudian evaluasi fungsi objektif. Tahap 6. Kembali ke tahap 3.

Baris fungsi objektif

$;

;

1

Variabel

2

basis dan

⋮

0

…

"<

"

Koefisien substitusi

profitnya

'

' /$;

Nilai

Variabel

dari

mana yang

variabel akan basis

meninggalkan basis

,

$, −

Variabel mana yang akan masuk ,

basis

Gambar 2.3 Tabel simpleks [Wu dan Coppins, 1981].

Pada bab selanjutnya akan dijelaskan pencarian sekuen konsensus pada sekuen DNA dengan mencari skor maksimum menggunkan pemrograman linier. Sekuen-sekuen DNA ini akan dimodelkan kedalam bentuk pemrograman linier.

2.5 Analisa Kompleksitas

Algoritma merupakan susunan proses yang digunakan untuk menyelesaikan masalah menggunakan komputer. Dan kompleksitas suatu algoritma adalah biaya, lamanya running time, memori yang dipakai, atau semua



13

unit yang berhubungan dengan penggunaan algoritma untuk menyelesaikan persoalan menggunakan komputer (Wilf, 1994). Proses komputasi memerlukan waktu untuk menyelesaikan masalah. Beberapa masalah kadang memerlukan banyak waktu, namun ada juga yang dapat diselesaikan dalam waktu yang cepat. Waktu yang digunakan dalam komputasi ini akan berbeda-beda tergantung dari jenis masalah yang digunakan. Untuk menghitung waktu kompleksitas dalam komputasi dapat dikukur dengan cara menyatakan ukuran running time sebagai suatu fungsi yang diproleh dari menghitung running time sejumlah data yang dibutuhkan untuk menggambarkan masalah (Wilf, 1994). Pada bab selanjutnya akan dibahas mengenai analisa kompleksitas. Pada analisa kompleksitas ini hanya akan dibahas mengenai running time yang dibutuhkan untuk menjalankan program yang telah dibuat.



BAB 3 IDENTIFIKASI SEKUEN KONSENSUS PADA SEKUEN DNA MENGGUNAKAN PEMROGRAMAN LINIER

Pada bab ini akan dibahas pencarian sekuen konsensus dari sekuen-sekuen DNA. Pada bab sebelumnya telah dijelaskan bahwa sekuen konsensus adalah sekuen dasar yang sering muncul di sekuen lainnya setelah sekuen-sekuen DNA itu disejajarkan. Pencarian sekuen konsensus ini menggunkan prinsip pencarian skor maksimum. Untuk mencari skor maksimum tersebut akan digunakan metode pemrograman linier yang telah dibahas dalam bab sebelumnya. Pada bab ini akan dijelaskan deskripsi masalah yang diberikan pada Subbab 3.1. Selanjutnya dibuat formulasi matematis yang kemudian dibentuk menjadi model pemrograman linier yang akan dibahas pada Subbab 3.2. Menggunakan contoh sekuen DNA yang diberikan, akan dibahas penyelesaian masalah dengan model pemrograman linier menggunakan metode simpleks yang akan dijelaskan pada Subbab 3.3.

3.1 Deskripsi Masalah Dari bagian tubuh suatu organisme, diambil sejumlah @ sekuen DNA.

Masing-masing sekuen DNA tersebut terdiri dari A buah basa. Kemudian akan dicari sekuen konsensus dari sekuen-sekuen DNA tersebut. Sekuen konsensus yang dicari ini terdiri dari 16 basa serta mempunyai pola 1, 2, … , 10.

. Dengan

,

{ , , , } untuk

merupakan gen promotor, sehingga keberadaan

=

ini dapat

diabaikan dari pembentukan sekuen konsensus. Sekuen DNA yang terdiri dari A basa ini dapat dibagi menjadi beberapa kandidat sekuen konsensus yang

masing-masing mempunyai 16 basa. Pencarian sekuen konsensus ini menggunakan teknik pemberian skor, sehingga untuk mendapatkan sekuen konsensus ini akan dicari skor maksimumnya. Dari masalah diatas, definisikan: @ A

= banyaknya sekuen DNA = banyaknya basa pada tiap sekuen DNA

14



15 = gen promotor { , , , }

{ , , , } untuk

= basa pada posisi dalam sekuen konsensus, = 1, 2, … , 10

“site” = letak kandidat sekuen konsesnsus pada sekuen DNA

B

C D

= posisi sekuen DNA = posisi basa pada sekuen DNA

= posisi awal kandidat sekuen konsensus pada sekuen DNA

3.2 Formulasi Matematika Sebanyak @ sekuen DNA yang masing-masing mempunyai A buah basa, dapat direpresentasikan dalam bentuk matriks sebagai berikut : ', H ' E=G , G⋮ F'K,

', ', ⋮ 'K,

… … ⋱ …

' '

,I

N

,I M

⋮M 'K,I L

Dimana 'O," adalah basa di posisi C pada sekuen DNA ke-B. Dengan B = 1,2, … , @

dan C = 1,2, … , A. Contoh 1:

Misalkan terdapat dua sekuen DNA yang masing-masing terdiri dari 18 basa. AAGACTGTTTTTTTGATC GATTATTTGCACGGCGTC Sekuen-sekuen DNA ini dapat direpresentasikan sebagai matriks menjadi: Q

E=P

Untuk mencari sekuen konsensus ini, terlebih dahulu akan ditentukan kandidat-kandidat sekuen konsensus yang mungkin dari setiap sekuen DNA. Masing-masing kandidat tersebut harus terdiri dari 16 basa. Misalkan dengan menggunakan sekuen DNA AAGACTGTTTTTTTGATC, akan dicari banyaknya kandidat sekuen konsensus. Posisi awal sekuen konsensus dimulai dari basa paling kiri pada sekuen DNA. Selanjutnya posisi awal sekuen konsensus berikutnya dimulai dari satu basa di sebelah kanan basa yang digunakan sebagai posisi awal sekuen konsensus sebelumnya. Berikut ini sekuen konsensus yang



16

diperoleh dengan menggunakan basa pertama, kedua dan ketiga dari sekuen DNA sebagai posisi awal kandidat sekuen konsensus. AAGACTGTTTTTTTGATC AAGACTGTTTTTTTGATC AAGACTGTTTTTTTGATC Ketika menggunakan basa ketiga di sekuen DNA sebagai posisi awal dari sekuen konsensus, basa terakhir sekuen DNA menjadi bagian kandidat sekuen konsensus tersebut. Akibatnya, ketika posisi awal sekuen konsensus di letakkan pada basa yang berada di sebelah kanan basa ketiga sekuen DNA, banyaknya kandidat sekuen konsensus yang terbentuk akan kurang dari 16, yaitu hanya mempunyai 15 basa. Sehingga secara umum banyaknya kandidat yang mungkin pada setiap sekuen DNA adalah (A − 16) + 1 = A − 15 kandidat.

Berdasarkan matriks E diatas, akan dibentuk matriks E’ yang berisi

kandidat-kandidat sekuen konsensus pada masing-masing sekuen DNA. Untuk memudahkan penulisan dan penghitungan, maka 6 gen promotor dapat diabaikan dan tidak ditulis dalam kandidat sekuen konsensus. Sehingga setiap kandidat sekuen konsensus hanya akan mempunyai masing-masing 10 buah basa. Matriks E’ yang dimaksud adalah:

R … R, H , … R , GR E′ = G , ⋮ G R … RK, F K,

Dimana

RO,T = U

R R

,

,

RK,

… R , … R ,I< … R , … R ,I< ⋮ ⋱ … RK, … RK,I<

S

S S

… R … R

,I<

,I<

⋮ … RK,I<

S

S S

N M M M L

'O, ST< (VCWVX = 1,2, … ,5) Z 'O, STS (VCWVX = 6,7, … ,10)

Dan D = 1,2, … , A − 15 merupakan posisi awal dari kandidat sekuen konsensus. Dari Contoh 1: AAGACTGTTTTTTTGATC GATTATTTGCACGGCGTC Banyaknya kandidat site yang mungkin untuk masing-masing sekuen

DNA adalah A − 15 = 18 − 15 = 3. Kandidat-kandidat site tersebut yaitu : B = 1, D = 1 AAGACTGTTTTTTTGATC B = 1, D = 2 AAGACTGTTTTTTTGATC



17 B = 1, D = 3 AAGACTGTTTTTTTGATC

B = 2, D = 1 GATTATTTGCACGGCGTC



Dari hasil yang diperoleh diatas, dibentuk matriks E’. Untuk mempermudah penulisan dan penghitungan selanjutnya, 6 gen promotor dari masing-masing kandidat sekuen konsensus tersebut akan diabaikan dan tidak ditulis. Matriks E′ yang terbentuk yaitu :

Q

E′ = P

Untuk membentuk model pemrograman linier, sebelumnya akan ditentukan variabel keputusan yang akan digunakan. Misalkan

adalah , maka . = 1,

posisi pada sekuen konsensus yang dicari dan jika jika

maka W = 1, jika

adalah

maka \ = 1, untuk

adalah

maka $ = 1, serta jika

= 1,2, … , 10. Selanjutnya

konsensus pada posisi s di sekuen ke-B dengan

adalah basa di

O,T

O,T

adalah

merupakan site sekuen

{0,1}.

konsensus pada site tersebut digunakan, sebaliknya

O,T

O,T

= 1 apabila sekuen

= 0 jika sekuen

konsensus pada site tersebut tidak digunakan. Sehingga . , W , $ , \ untuk = 1, 2, … , 10, dan

untuk B=1, 2, …, @ dan D=1, 2, …, A-15, akan digunakan

O,T

sebagai variabel keputusan pada pemrograman linier. Kemudian akan dibentuk fungsi objektif untuk menghasilkan skor maksimum. Nilai optimal diperoleh dengan memaksimumkan hasil penjumlahan dari semua DX]Ô . DX]Ô adalah skor pada sekuen DNA ke-B.

skor akhir = maks DX]^_W]W.B = maks ∑KO- DX]Ô

(3.1)

Berdasarkan Contoh 1:

DX]^ =

DX]^ =

,

,

(. + . + \ + . + $ + W + W + W + \ + . ) +

,

(. + \ + . + $ + W + W + W + \ + . + W )

+

,

(\ + . + $ + W + \ + W + \ + . + W + $ )

+

,

(. + W + W + . + W + \ + \ + $ + \ + W )

(\ + . + W + W + . + $ + \ + \ + $ + \ ) +

,

(W + W + . + W + W + \ + $ + \ + W + $ )



18 DX]^_W]W.B = . h

,

+. h

+. h +$ h

+ ,

+

+

+

+

,

,

,

+

,

,

,

+

,

,

,

,

i+$ h

,

+

+

,

i+. h

i+$ h

,

,

i+W h

i+\ h

,

,

,

+

+

,

i+\ h

i+W h +

+

,

,

i+ \ h

,

+

,

,

i+\ h

,

i+$ h

,

,

,

+W h

+

i+W h

+W h

+. h

,

,

,

+\ h

+

+

,

+W h

+W h

+

,

+

+

,

,

i+\ h

,

+

,

,

,

,

,

+

i

,

i+\ h

,

i+. h

i

i

+

,

i+$ h

i+$ h

,

,

,

i+$ h

i+$ h ,

i+W h

i+. h

,

,

i+W h

,

i

i+W h

i+\ h

i+. h

i+\ (

,

)

,

+

,

i

,

+

,

,

,

,

i

i

i

i

Sehingga fungsi objektif untuk mengidentifikasi sekuen konsensus dapat ditulis menjadi:

skor akhir = maks ∑ {. ∑(O,T)jklm \ ∑(O,T)jkpm

Dimana q dan q

= {(B, D)|RO,T = }, q

O,T

O,T }

+ W ∑(O,T)jkom

O,T

= {(B, D)|RO,T = }, q

+ $ ∑(O,T)jknm

+

O,T

(3.2)

= {(B, D)|RO,T = }

= {(B, D)|RO,T = }, dengan = 1, 2, … , 10 , B = 1, 2, … , @ dan D =

1, 2, … , A − 15.

Fungsi objektif pada (3.2) masih mengandung persamaan nonlinier

dimana A ∑

O,T

untuk A { , , , }. Bentuk perkalian ini dapat dilinierisasikan

dengan proposisi berikut.

Proposisi 3.1. Bentuk perkalian s = A ∑ dan A {. , $ , \ , W } serta

O,T , A

O,T

dengan s untuk memaksimumkan

{0,1} dapat dilinierisasikan sebagai berikut : s ≥0

s ≤∑

(3.3) O,T

(3.4)

s ≤ tA

(3.5)

untuk = 1, 2, . . , 10, B = 1, 2, … , @, dan D = 1,2, … , A − 15. Dimana t adalah konstanta yang lebih besar atau sama dengan banyaknya sekuen DNA. Bukti.

Diketahui A , ,

s =∑

O,T ,

O,T

{0,1}, sehingga untuk s = A ∑

O,T ,

selain itu A = 0 mengakibatkan s = 0. ∎

jika A = 1 maka



19

Selanjutnya notasikan :

(. ) = . ∑(O,T)∈klm

(W ) = W ∑(O,T)∈kom

($ ) = $ ∑(O,T)∈knm

(\ ) = \ ∑(O,T)∈kpm

O,T

(3.6)

O,T

(3.7)

O,T

(3.8)

O,T

(3.9)

Berdasarkan Proposisi 3.1 substitusi persamaan (3,6), (3.7), (3.8) dan (3.9) ke dalam persamaan (3.3) dan (3.5) pada Proposisi 3.1 menjadi : (. ) ≤ t.

(3.10)

(W ) ≤ tW

(3.11)

($ ) ≤ t$

(3.12)

(\ ) ≤ t\

(3.13)

(. ), (W ), ($ ), (\ ) ≥ 0

(3.14)

Fungsi objektif yang diperoleh adalah : skor akhir = maks DX]^_W]W.B

K = maks ∑O- DX]Ô = maks ∑ - ( (. ) + (W ) + ($ ) + (\ ))

Dengan syarat

(3.15)

(. ) ≤ t.

(W ) ≤ tW ($ ) ≤ t$

(\ ) ≤ t\

(. ), (W ), ($ ), (\ ) ≥ 0

Setelah ditentukan variabel keputusan dan fungsi objektif, kemudian tentukan fungsi-fungsi kendala yang diperlukan. 1. Fungsi kendala yang berhubungan dengan posisi basa pada sekuen konsensus.Setiap basa sekuen konsensus

hanya dapat ditempati oleh

satu basa. Misalkan jika basa sekuen konsensus

=

maka . = 1

dan $ = W = \ = 0. Sehingga akan memberika syarat : Untuk = 1, 2, … , 10.

. +$ +W +\ =1

(3.16)



20

2. Fungsi kendala yang berhubungan dengan site pada sekuen DNA untuk menentukan kandidat sekuen konsensus yang akan digunakan. Dalam menentukan sekuen konsensus akan dihitung skor dari tiap-tiap sekuen DNA. Setiap sekuen DNA hanya akan mempunyai satu sekuen konsensus, sehingga untuk menghasilkan DX]Ô pada setiap sekuen ke – B hanya satu site yang diplih dan tidak ada site lain selain site

tersebut yang digunakan.

DX]Ô = ∑I< T-

Dimana wO,T

O,T

hwO,T + wO,T + … + wO,T i

. , | X. RO,T = { y W , | X. RO,T = Z = z $ , | X. RO,T = y x\ , | X. RO,T =

Misalkan site ke – X dipilih sehingga

O,}

= 1 dan

O,T

(3.17)

= 0 untuk

X {1, 2, … , A − 15} dan D {1,2, … , A − 15) serta D ≠ X. Sehingga menghasilkan kendala :

I< ∑T-

O,T

O,T

=1

(3.18)

{0,1}

Untuk B = 1, 2, … , @ dan D = 1, 2, … , A − 15, juga mengakibatkan

0 ≤ DX]Ô ≤ 10.

Dari variabel keputusan, fungsi kendala dan fungsi objektif di persamaan (3.10) – (3.15), (3.16) dan (3.18), diperoleh model pencarian sekuen konsensus yang berupa pemrograman linier, yaitu : Fungsi objektif

K DX]^ W]W.B = 0.XD ∑O- DX]Ô = ∑ - ( (. ) + (W ) + ($ ) + (\ ))

Dengan syarat

(. ) ≤ t.

(W ) ≤ tW ($ ) ≤ t$

(\ ) ≤ t\



21 (. ), (W ), ($ ), (\ ) ≥ 0

∑I< T-

O,T

O,T

=1

{0, 1}

untuk B =, 1, 2, … , @ dan D =, 1, … , A − 15 . +W +$ +\ =1 . , W , $ , \ {0, 1}

untuk = 1,2, … ,10 Nilai optimal diperoleh ketika fungsi objektif bernilai maksimum. Variabel-variabel keputusan yang memaksimumkan fungsi objektif merupakan solusi dari pemrograman linier. Sekuen konsensus ditentukan dari nilai variabel keputusan yang didapatkan.

3. 3 Penyelesaian Masalah

Masalah pemrograman linier dapat dapat diselesaikan dengan beberapa metode, salah satunya metode simpleks. Berdasarkan contoh sebelumnya, akan dicari sekuen konsensus menggunakan pemrograman linier dan akan diselesaikan dengan metode simpleks. Dengan menggunakan sekuen DNA pada Contoh 1, yaitu: AAGACTGTTTTTTTGATC GATTATTTGCACGGCGTC

Kandidat sekuen konsensusn tersebut diberikan dalam matriks E′. E• = P

Kemudian bentuklah persamaan pemrograman linier berdasarkan nilai

Q

O,T

pada

masing-masing sekuen DNA. Untuk

,

= 1 dan

,

= 1,

AAGACTGTTTTTTTGATC GATTATTTGCACGGCGTC

B = 1 dan D = 1 AAGACTTTGA

B = 2 dan D = 1 GATTACGGCG Universitas Indonesia


22

Ubahlah sekuen diatas menjadi model pemrograman linier.

DX]^ = . + . + \ + . + $ + W + W + W + \ + .

Maks

+\ +

. +W +W +. +$ +\ +\ +$ +\ . +$ +W +\ =1 . ,\ ,W ,$

{0,1}

untuk = 1,2, … ,10 Tahap 1, bentuk masalah pemrograman linier kedalam bentuk standar

dengan menambahkan sejumlah 0 variabel artifisial. Karena fungsi kendala berbentuk sama dengan, maka variabel artifisial mempunyai koefisien – t. DX]^ = . + . + \ + . + $ + W + W + W + \ + .

Maks

W +W +. +$ +\ +\ +$ +\ t

−t

−t

−t

−t

. +$ +W +\ −t

. , $ , W , \ {0,1}

−t

−t

−t

=1

+\ +. +

−t

−t

−

untuk = 1,2, … ,10

,

,

Tahap 2, terdapat 10 kendala sehingga 0 = 10, gunakan variabel slack ,

,

,

,

,

,

dan

untuk membentuk basis awal solusi layak, = 1,

sedangkan variabel yang bukan dasar bernilai nol. Sehingga 1,

= 1,

= 1,

= 1,

= 1,

= 1,

= 1 dan

= 1,

=

= 1. Tabel dapat dilihat

di Tabel Lampiran 1.1. Tahap 3, tentukan variabel yang akan masuk basis. Variabel yang masuk

adalah variabel dengan $, −

,

positif terbesar. Jika tidak ada, solusi sudah

optimal. Kolom dari variabel yang akan masuk disebut kolom pivot.

Tahap 4, tentukan variabel yang akan keluar basis. Misalkan w, telah

dipilih sebagai variabel yang masuk. Variabel dengan min ' /. , dimana '

adalah konstanta di sebelah kanan fungsi kendala dan . , adalah koefisien pada kolom w, , akan keluar dari basis dan baris ini disebut baris pivot. ' /. , untuk

suatu dipertimbangkan jika . , positif. Perpotongan antara kolom pivot dan baris

pivot disebut elemen pivot.

Tahap 5, lakukan sejumlah operasi baris yang mengeliminasi w ∗ (variabel

masuk) dari seluruh baris kecuali baris pivot , dengan cara membagi baris pivot



23

dengan elemen pivot, diperoleh baris baru pivot. Untuk baris lainnya (bukan pivot), berlaku:

Baris ke- baru = baris lama – . , (baris baru pivot). Tabel simpleks pada Tabel Lampiran 1.1 setelah mengalami pivoting dapat dilihat pada Tabel Lampiran 1.2. Tahap 6, kembali ke tahap 3, ulangi proses yang telah dilakukan sebelumnya. Lakukan sampai solusi benar-benar optimal. Setelah 10 iterasi, hasil akhir simpleks ditunjukkan pada Tabel Lampiran 1.3. Tabel akhir simpleks = 1 dan

menunjukkan bahwa untuk

,

. ,W ,W ,$ ,W ,\ ,\ ,$ ,.

= 1.

,

= 1 menghasilkan solusi optimal

dengan nilai fungsi objektif 11 dan nilai . = 2, serta Dengan mengulangi proses diatas untuk dan ,

,

= 1,

= 1 dan

,

,

= 1dan

= 1,

,

,

= 1,

,

= 1 dan

,

= 1 dan

= 1, serta

,

,

= 1 dan ,

= 1,

,

,

= 1,

= 1 dan

= 1 dan

,

= 1,

,

,

=1

= 1,

menghasilkan tabel akhir simpleks yang ditunjukkan dalam Tabel Lampiran 1.4 sampai Tabel Lampiran 1.11. Hasilnya diringkas pada tabel berikut :

Tabel 3.1 ringkasn nilai fungsi objektif tabel akhir simpleks , , ,

,

,

,

11

11

14

13

13

11

10

13

13

Berdasarkan Tabel 3.1, nilai fungsi objektif yang paling maksimum diperoleh ketika menggunkan

,

= 1 dan

,

= 1, dengan nilai fungsi objektif

14 dan \ = . = W = \ = 2 serta $ = \ = W = \ = $ = \

= 1.

Sehingga dapat disimpulkan bahwa sekuen konsensus dari sekuen DNA pada Contoh 1 adalah GATTATGATC. Pada sekuen DNA pertama sekuen konsensus

terdapat di posisi D = 3 dan pada sekuen DNA kedua, sekuen konsensus terdapat

di posisi D = 1.



BAB 4 IMPLEMENTASI PROGRAM

Dalam memecahkan masalah pencarian sekuen konsensus dengan pemrograman linier, penyelesaian secara manual tidak efisien, karena memerlukan penghitungan yang banyak dan waktu yang cukup lama. Karena itu, menyelesaikan masalah ini dapat dilakukan dengan program yang dibuat. Pada bab ini akan diberikan simulasi penyelesaian masalah pencarian sekuen konsensus menggunakan program MATLAB versi 5.3.1 dan komputer berprosesor intel atom N270 @1,60 GHz RAM 1,00 GB, listing program diberikan pada Lampiran 3. Di Bab 3, telah diberikan contoh pencarian sekuen secara manual menggunakan sekuen DNA pada Contoh 1. Pada Subbab 4.1 akan diberikan simulasi program untuk menyelesaikan masalah yang sama. Selanjutnya akan dilakukan analisa terhadap program yang akan dijelaskan pada Subbab 4.2. Program MATLAB untuk mencari sekuen konsensus dijalankan dengan algoritma : Tahap 1 Masukkan input berupa sekuen DNA. Tahap 2 Tentukan kandidat-kandidat sekuen konsensus tanpa gen promotor dari setiap sekuen. Tahap 3 Bentuk matriks yang berisi kandidat-kandidat sekuen konsensus, matriks berukuran × |, dimana banyaknya sekuen dan | banyaknya kandidat

pada tiap sekuen. Tahap 4 Ambil satu kandidat dari setiap sekuen, bentuk fungsi objektifnya dan maksimumkan nilai fungsi objektif. Tahap 5 bandingkan semua hasil yang diperoleh, dan pilih nilai yang paling maksimum. Tahap 6 Tentukan sekuen konsensus berdasarkan nilai maksimum yang diperoleh.

Algoritma ini diterapkan pada pseudocode berikut % Tahap 1 input masukkan banyaknya sekuen p = banyaknya sekuen DNA % Tahap 2

24



25

for j=1:p Input masukkan sekuen ke –j hitung banyaknya basa tiapa sekuen ke-j kolom(j)=banyaknya basa sekuen ke-j k(j)=kolom(j)-15 end for % Tahap 3 for j=1:p for i=1:k(j) x{i,j}= 5 basa awal kandidat sekuen konsensus y(i,j}= 5 basa akhir kandidat sekuen konsensus Bentuk matriks yang berisi kandidat-kandidat sekuen konsensus D{i,j}=[x{i,j} y(i,j}] end for end for definisikan hmax=-9999 % Tahap 4 for z1=1:i for z2=1:i for z3=1:i bentuk fungsi objektif f= [(1,z1) (2,z2) (3,z3)] pilih basa di tiap-tiap posisi yang memberikan kontribusi terbesar pada fungsi objektif evaluasi nilai fungsi objektif h = nilai fungsi objektif % Tahap 5 if h≥hmaks hmaks=h else hmaks=hmaks end if end for end for end for % Tahap 6 hmaks, sekuen konsensus dan posisinya



26

4.1 Simulasi Program

Untuk simulasi awal digunakan data dummy pada Contoh 1 di Bab 3 yang berupa 2 sekuen DNA dengan masing-masing 18 basa yaitu :

AAGACTGTTTTTTTGATC GATTATTTGCACGGCGTC Kemudian akan dicari sekuen konsensusnya menggunkan program yang telah dibuat. Untuk menjalankan program ini, buka terlebih dahulu software MATLAB, kemudian ketik “sekuen2” pada command window. Tentukan banyaknya sekuen DNA serta masukkan sekuen DNA. Setelah semua sekuen DNA dimasukkan, tekan enter untuk melihat hasilnya.

Gambar 4.1 Tampilan masukan dan keluaran untuk dua sekuen DNA

Hasil pada Gambar 4.1 menunjukkan bahwa sekuen konsensus yang diperoleh adalah GATTATGATC dengan nilai maksimum 14 serta terletak pada posisi 3 di sekuen pertama dan berada di posisi 1 untuk sekuen kedua. Waktu yang diperlukan untuk memperoleh hasilnya adalah 0,038 detik.



27

4.2 Analisa Kompleksitas

Di subbab sebelumnya telah dilakukan simulasi program dengan dua sekuen DNA yang masing-masing mempunyai 18 basa. Running program ini memerlukan waktu 0,038 detik. Sekuen DNA tersebut merupakan data dummy yang digunakan untuk percobaan. Pada subbab ini akan dianalisa running program menggunakan data real berupa sekuen DNA bakteri E.Coli. Data ini terdiri dari 18 sekuen yang masing-masing mempunyai 105 basa. Daftar sekuen DNA dapat dilihat di Lampiran 2. Selanjutnya akan dicari estimasi waktu untuk mendapatkan sekuen konsensus dari sekuen DNA E.Coli tersebut. Hal pertama yang akan dilakukan adalah menghitung waktu peritersi berdasarkan banyaknya iterasi. Satu iterasi di hitung sebagai sekali proses penghitungan nilai optimal pemrograman linier dari kombinasi setiap satu kandidat dari masing-masing sekuen DNA yang ada. Proses ini akan dilakukan terus sampai semua kandidat habis dikombinasikan. Sehingga banyaknya iterasi dalam satu kali running untuk

memperoleh sekuen konsensus adalah (A − 15)K , dengan @ adalah banyaknya

sekuen DNA dan A adalah banyaknya basa pada tiap sekuen DNA. Waktu rata-

rata periterasi dihitung dengan menghitung total waktu yang dibutuhkan untuk sekali mendapatkan sekuen konsensus kemudian dibagi dengan total banyaknya iterasi.

Gambar 4.2 Grafik waktu periterasi terhadap banyaknya iterasi



28

Sumbu

pada Gambar 4.2 menyatakan banyaknya iterasi dan sumbu ƒ

menyatakan waktu rata-rata yang diperlukan untuk melakukan sekali iterasi jika iterasi sebanyak

dilakukan. Berdasarkan Gambar 4.2 waktu rata-rata yang

dibutuhkan untuk sekali iterasi tidak lebih dari 0,012 detik. Selanjutnya untuk menghitung waktu yang dibutuhkan untuk running program dengan data real sekuen DNA E.Coli pada Lampiran 2, diasumsikan jika waktu rata-rata sekali iterasi adalah 0,012 detik.

Tabel 4.1 Estimasi waktu running program Total

Estimasi waktu yang dibutuhkan jika menggunakan @ sekuen

iterasi

detik

90

8100

2,7

105

90

729000

243

4,05

105

90

6,56x107

21870

364,5

6.075

32805

546,75

22,78125

@

A

q-15

2

105

3 4 5 6 7

105 105 105

90 90 90

5,9x10

9

5,34x10

11

4,78x10

13

15

menit

1968300

jam

hari

bulan

8

2952450

49207,5

2050,31

68,34375

1,59x10

10

8

4428675

184528

6150,938

1,43x10

12

10

8

1,77x10

2,66x10 2,39x10

3,99x10

1,66x10

7

5,5x105

8

105

90

4,3x10

9

105

90

3,87x1017

1,29x1014

2,15x1012

3,59x1010

1,49x109

4,9x107

10

105

90

3,49x1019

1,16x1016

1,94x1014

3,23x1012

1,35x1011

4,4x109

11

105

90

3,14x1021

1,05x1018

1,74x1016

2,91x1014

1,21x1013

4,04x1011

12

105

90

2,82x1023

9,41x1019

1,57x1018

2,62x1016

1,09x1015

3,63x1013

13

105

90

2,54x1025

8,47x1021

1,41x1020

2,35x1018

9,81x1016

3,27x1015

14

105

90

2,29x1027

7,63x1023

1,27x1022

2,12x1020

8,83x1018

2,94x1017

15

105

90

2,06x1029

6,86x1025

1,14x1024

1,91x1022

7,94x1020

2,65x1019

16

105

90

1,85x1031

6,18x1027

1,03x1026

1,72x1024

7,15x1022

2,38x1021

17

105

90

1,67x1033

5,56x1029

9,27x1027

1,54x1026

6,43x1024

2,14x1023

18

105

90

1,5x1035

5x1031

8,34x1029

1,39x1028

5,79x1026

1,93x1025

Pada Tabel 4.1 dapat dilihat hasil simulasi waktu yang dibutukan untuk running program apabila kita menggunakan 2 sampai 18 sekuen DNA E.Coli. Untuk menyelesaikan masalah pencarian sekuen konsensus menggunakan data yang semakin besar ternyata memerlukan waktu yang semakin lama. Berdasarkan hasil simulasi pada Tabel 4.1, jumlah sekuen yang memungkinkan masih bisa dieksekusi program ini adalah maksimum 5 sekuen DNA dalam sekali running.



29

Berikut ini sebagai contoh akan dicoba running program untuk 2 sekuen dan 3 sekuen DNA E.Coli dengan waktu running tidak terlalu lama.

Gambar 4.3 Tampilan masukkan dan keluaran untuk 2 sekuen DNA E.coli

Gambar 4.4 Tampilan masukkan dan keluaran untuk 3 sekuen DNA E.coli

Berdasarkan Gambar 4.3 dan Gambar 4.4, dengan menggunakan 2 sekuen dan 3 sekuen DNA diperoleh sekuen konsensus yang sama yaitu TTTGATCACA dan dengan posisi yang sama yaitu terletak di posisi 64 untuk sekuen pertama, di posisi 58 untuk sekuen kedua dan di posisi 79 untuk sekuen ketiga. Waktu yang



30

diperlukan untuk running adalah 2,0310 detik untuk 2 sekuen dan 208,1570 detik untuk 3 sekuen. Waktu ini tidak berbeda jauh dari estimasi waktu yang telah diberikan pada Tabel 4.2 yaitu 2,7 detik untuk 2 sekuen dan 243 detik untuk 3 sekuen. Sementara itu berdasarkan hasil estimasi waktu pada Tabel 4.2, untuk mencari sekuen konsensus dengan menggunakan 18 sekuen diperlukan waktu yang sangat lama sehingga tidak dilakukan dalam skripsi ini.



BAB 5 PENUTUP

5.1 Kesimpulan

Dalam skripsi ini pencarian sekuen konsensus dapat dicari menggunakan pemrograman linier. Sekuen konsensus diperoleh ketika nilai fungsi objektif bernilai maksimum. Letak sekuen konsensus diketahui melalui nilai

O,T

yang

digunakan pada tiap sekuen DNA untuk memaksimumkan nilai fungsi objektif.

Serta sekuen konsensus ditentukan melalui nilai . , $ , W dan \ untuk =

1, 2, … , 10 yang mengakibatkan nilai fungsi objektif menjadi maksimum.

Pencarian sekuen konsensus ini dapat dilakukan menggunakan program. Dengan menggunkan sekuen DNA pada Bab 3, cara manual maupun menggunakan program memberikan hasil yang sama yaitu diperoleh sekuen

konsensus GATTATGATC dengan posisi D = 3 untuk sekuen pertama dan D = 1 untuk sekuen kedua. Penyelesaian menggunakan program ini memerlukan waktu 0,038 detik. Ketika menggunakan data real berupa sekuen DNA E.Coli, untuk 2 sekuen DNA, waktu running cukup singkat yaitu 2,7 detik. Namun ketika menggunakan 18 sekuen DNA, estimasi waktu running yang diperlukan sangat lama yaitu sekitar 5x1031 detik. Berdasarkan estimasi waktu pada Tabel 4.1, program ini hanya mampu melakukan running sampai 5 sekuen DNA E.Coli.

5.2 Saran

Dalam dunia bioinformatika umumnya bekerja dengan data sekuen DNA yang sangat banyak. Penyelesaian masalah sekuen konsensus dengan pemrograman linier untuk data yang besar akan memerlukan waktu running yang sangat lama. Ini merupakan kelemahan dari program tersebut karena berjalan secara serial. Salah satu solusi yang bisa digunakan adalah menggunakan teknik komputasi tingkat lanjut berbasis komputasi paralel. Untuk penelitian selanjutnya disarankan menggunakan komputasi paralel sehingga waktu running dapat dipersingkat.

31



DAFTAR PUSTAKA

Brazma, Alvis, et al.(1998).Approaches to the Automatic Discovery of Patterns in Biosequences.Journal of Computational Biology 5, 279-305. Bronsosn, Richard.(1998).Teori dan Soal-soal Operation Research.(Drs. Hans J. Wospakrik, penerjemah).Jakarta:Erlangga. Ecker, J.G. et al.(2002).An Aplication of Non-linear Optimization in Molecular Biology.Europe Journal of Operational Research 138, 452-458. Han-Lin Li & Chang-Jui Fu.(2005).A Linear Programming Approach for Identifyng a Consensus sequence on DNA Sequences.Oxford University Press 21, 1838-1845. Schrage.(1999).Optimization Modeling with Lingo.Chicago:LINDO System Inc.

Scheider, Thomas.D.(2002).Consensus Sequence Zen.National Cancer Institute 1, 111-119. Wilf, Herbert, S.Algorithms and Complexity.1994. 10 Juni 2012. www.math.upenn.edu/~Wilf/AlgoComp.pdf Winston, Wayne.(1995).Introduction to Mathematical Programming. California:Duxbury Press. Wu, Nesa & Coppins, Richard.(1981).Linear Programming and Extensions.USA:McGraw-Hill. Yi-Ping.(1998).Bioinformatics Technologies.Australia:Springer.

32



33

Tabel Lampiran 1.1. Tabel awal simpleks untuk ‫ݖ‬ଵǡଵ ൌ ͳ dan ‫ݖ‬ଶǡଵ ൌ ͳ

Lampiran 1. Tabel Simpleks



34

Tabel Lampiran 1.2. Tabel kedua simpleks untuk ‫ݖ‬ଵǡଵ ൌ ͳ dan ‫ݖ‬ଶǡଵ ൌ ͳ

(lanjutan)



35

(lanjutan)

Tabel Lampiran 1.3 Tabel akhir simpleks untuk ‫ݖ‬ଵǡଵ ൌ ͳ dan ‫ݖ‬ଶǡଵ ൌ ͳ



36

Tabel Lampiran 1.4. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଵ ൌ ͳ dan ‫ݖ‬ଶǡଶ ൌ ͳ

(lanjutan)



37

Tabel Lampiran 1.5. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଵ ൌ ͳ dan ‫ݖ‬ଶǡଷ ൌ ͳ

(lanjutan)



38

(lanjutan)

Tabel Lampiran 1.6. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଶ ൌ ͳ dan ‫ݖ‬ଶǡଵ ൌ ͳ



39

Tabel Lampiran 1.7. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଶ ൌ ͳ dan ‫ݖ‬ଶǡଶ ൌ ͳ

(lanjutan)



40

Tabel Lampiran 1.8. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଶ ൌ ͳ dan ‫ݖ‬ଶǡଷ ൌ ͳ

(lanjutan)



41

Tabel Lampiran 1.9. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଷ ൌ ͳ dan ‫ݖ‬ଶǡଵ ൌ ͳ

(lanjutan)



42

Tabel Lampiran 1.10. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଷ ൌ ͳ dan ‫ݖ‬ଶǡଶ ൌ ͳ

(lanjutan)



43

Tabel Lampiran 1.11. Tabel akhir simpleks untuk ‫ݖ‬ଵǡଷ ൌ ͳ dan ‫ݖ‬ଶǡଷ ൌ ͳ

(lanjutan)



44

Lampiran 2. Daftar sekuen DNA •

•

•

•

•

•

•

•

•

•

E.coli

TAATGTTTGTGCTGGTTTTTGTGGCATCGGGCGAGAATAGCGCG TGGTGTGAAAGACTGTTTTTTTGATCGTTTTCACAAAAATGGAA GTCCACAGTCTTGACAG GACAAAAACGCGTAACAAAAGTGTCTATAATCACGGCAGAAAA GTCCACATTGATTATTTGCACGGCGTCACACTTTGCTATGCCAT AGCATTTTTATCCATAAG ACAAATCCCAATAACTTAATTATTGGGATTTGTTATATATAACT TTATAAATTCCTAAAATTACACAAAGTTAATAACTGTGAGCATG GTCATATTTTTATCAAT CACAAAGCGAAAGCTATGCTAAAACAGTCAGGATGCTACAGTA ATACATTGATGTACTGCATGTATGCAAAGGACGTCACATTACCG TGCAGTACAGTTGATAGC ACGGTGCTACACTTGTATGTAGCGCATCTTTCTTTACGGTCAAT CAGCAAGGTGTTAAATTGATCACGTTTTAGACCATTTTTTCGTC GTGAAACTAAAAAAACC AGTGAATTATTTGAACCAGATCGCATTACAGTGATGCAAACTTG TAAGTAGATTTCCTTAATTGTGATGTGTATCGAAGTGTGTTGCG GAGTAGATGTTAGAATA GCGCATAAAAAACGGCTAAATTCTTGTGTAAACGATTCCACTAA TTTATTCCATGTCACACTTTTCGCATCTTTGTTATGCTATGGTTA TTTCATACCATAAGCC GCTCCGGCGGGGTTTTTTGTTATCTGCAATTCAGTACAAAACGT GATCAACCCCTCAATTTTCCCTTTGCTGAAAAATTTTCCATTGTC TCCCCTGTAAAGCTGT AACGCAATTAATGTGAGTTAGCTCACTCATTAGGCACCCCAGGC TTTACACTTTATGCTTCCGGCTCGTATGTTGTGTGGAATTGTGAG CGGATAACAATTTCAC ACATTACCGCCAATTCTGTAACAGAGATCACACAAAGCGACGG TGGGGCGTAGGGGCAAGGAGGATGGAAAGAGGTTGCCGTATAA AGAAACTAGAGTCCGTTTA Universitas Indonesia


45

•

•

•

•

•

•

•

•

GGAGGAGGCGGGAGGATGAGAACACGGCTTCTGTGAACTAAAC CGAGGTCATGTAAGGAATTTCGTGATGTTGCTTGCAAAAATCGT GGCGATTTTATGTGCGCA GATCAGCGTCGTTTTAGGTGAGTTGTTAATAAAGATTTGGAATT GTGACACAGTGCAAATTCAGACACATAAAAAAACGTCATCGCT TGCATTAGAAAGGTTTCT GCTGACAAAAAAGATTAAACATACCTTATACAAGACTTTTTTTT CATATGCCTGACGGAGTTCACACTTGTAAGTTTTCAACTACGTT GTAGACTTTACATCGCC TTTTTTAAACATTAAAATTCTTACGTAATTTATAATCTTTAAAAA AAGCATTTAATATTGCTCCCCGAACGATTGTGATTCGATTCACA TTTAAACAATTTCAGA CCCATGAGAGTGAAATTGTTGTGATGTGGTTAACCCAATTAGAA TTCGGGATTGACATGTCTTACCAAAAGGTAGAACTTATACGCCA TCTCATCCGATGCAAGC CTGGCTTAACTATGCGGCATCAGAGCAGATTGTACTGAGAGTGC ACCATATGCGGTGTGAAATACCGCACAGATGCGTAAGGAGAAA ATACCGCATCAGGCGCTC CTGTGACGGAAGATCACTTCGCAGAATAAATAAATCCTGGTGTC CCTGTTGATACCGGGAAGCCCTGGGCCAACTTTTGGCGAAAATG AGACGTTGATCGGCACG GATTTTTATACTTTAACTTGTTGATATTTAAAGGTATTTAATTGT AATAACGATACTCTGGAAAGTATTGAAAGTTAATTTGTGAGTGG TCGCACATATCCTGTT



46

Lampiran 3.

Listing

Program

p=input('Masukkan banyak sekuen: '); for j=1:p Sekuen{j}=input(['Masukkan sekuen DNA ke-' int2str(j) ' : '], 's'); [baris(j) kolom(j)]=size(Sekuen{j}); k(j)=kolom(j)-15; fprintf(['banyaknya basa sekuen ke-' int2str(j) ': %d \n'],kolom(j)); end for j=1:p for i=1:k(j) x{j,i}=Sekuen{j}(i:(i+4)); y{j,i}=Sekuen{j}((i+11):(i+15)); d{j,i}=[x{j,i} y{j,i}] ; end end hmax=-9999; posisi=[]; for z1=1:i for z2=1:i for z3=1:i e=([d(1,z1) d(2,z2) d(3,z3)]); pos1=z1; pos2=z2; pos3=z3; f=char(e); g=f'; ea1=findstr(g(1,:),'a'); [rowa1 cola1]=size(ea1); et1=findstr(g(1,:),'t'); [rowt1 colt1]=size(et1); ec1=findstr(g(1,:),'c'); [rowc1 colc1]=size(ec1); eg1=findstr(g(1,:),'g'); [rowg1 colg1]=size(eg1); h1=max([cola1 colt1 colc1 colg1]); if h1==cola1 L1='a'; elseif h1==colt1



47

L1='t'; elseif h1==colc1 L1='c'; else L1='g'; end ea2=findstr(g(2,:),'a'); [rowa2 cola2]=size(ea2); et2=findstr(g(2,:),'t'); [rowt2 colt2]=size(et2); ec2=findstr(g(2,:),'c'); [rowc2 colc2]=size(ec2); eg2=findstr(g(2,:),'g'); [rowg2 colg2]=size(eg2); h2=max([cola2 colt2 colc2 colg2]); if h2==cola2 L2='a'; elseif h2==colt2 L2='t'; elseif h2==colc2 L2='c'; else L2='g'; end ea3=findstr(g(3,:),'a'); [rowa3 cola3]=size(ea3); et3=findstr(g(3,:),'t'); [rowt3 colt3]=size(et3); ec3=findstr(g(3,:),'c'); [rowc3 colc3]=size(ec3); eg3=findstr(g(3,:),'g'); [rowg3 colg3]=size(eg3); h3=max([cola3 colt3 colc3 colg3]); if h3==cola3 L3='a'; elseif h3==colt3 L3='t'; elseif h3==colc3 L3='c'; else L3='g'; end ea4=findstr(g(4,:),'a'); [rowa4 cola4]=size(ea4); et4=findstr(g(4,:),'t'); [rowt4 colt4]=size(et4); ec4=findstr(g(4,:),'c');



48

[rowc4 colc4]=size(ec4); eg4=findstr(g(4,:),'g'); [rowg4 colg4]=size(eg4); h4=max([cola4 colt4 colc4 colg4]); if h4==cola4 L4='a'; elseif h4==colt4 L4='t'; elseif h4==colc4 L4='c'; else L4='g'; end ea5=findstr(g(5,:),'a'); [rowa5 cola5]=size(ea5); et5=findstr(g(5,:),'t'); [rowt5 colt5]=size(et5); ec5=findstr(g(5,:),'c'); [rowc5 colc5]=size(ec5); eg5=findstr(g(5,:),'g'); [rowg5 colg5]=size(eg5); h5=max([cola5 colt5 colc5 colg5]); if h5==cola5 L5='a'; elseif h5==colt5 L5='t'; elseif h5==colc5 L5='c'; else L5='g'; end ea6=findstr(g(6,:),'a'); [rowa6 cola6]=size(ea6); et6=findstr(g(6,:),'t'); [rowt6 colt6]=size(et6); ec6=findstr(g(6,:),'c'); [rowc6 colc6]=size(ec6); eg6=findstr(g(6,:),'g'); [rowg6 colg6]=size(eg6); h6=max([cola6 colt6 colc6 colg6]); if h6==cola6 L6='a'; elseif h6==colt6 L6='t'; elseif h6==colc6 L6='c'; else



49

L6='g'; end ea7=findstr(g(7,:),'a'); [rowa7 cola7]=size(ea7); et7=findstr(g(7,:),'t'); [rowt7 colt7]=size(et7); ec7=findstr(g(7,:),'c'); [rowc7 colc7]=size(ec7); eg7=findstr(g(7,:),'g'); [rowg7 colg7]=size(eg7); h7=max([cola7 colt7 colc7 colg7]); if h7==cola7 L7='a'; elseif h7==colt7 L7='t'; elseif h7==colc7 L7='c'; else L7='g'; end ea8=findstr(g(8,:),'a'); [rowa8 cola8]=size(ea8); et8=findstr(g(8,:),'t'); [rowt8 colt8]=size(et8); ec8=findstr(g(8,:),'c'); [rowc8 colc8]=size(ec8); eg8=findstr(g(8,:),'g'); [rowg8 colg8]=size(eg8); h8=max([cola8 colt8 colc8 colg8]); if h8==cola8 L8='a'; elseif h8==colt8 L8='t'; elseif h8==colc8 L8='c'; else L8='g'; end ea9=findstr(g(9,:),'a'); [rowa9 cola9]=size(ea9); et9=findstr(g(9,:),'t'); [rowt9 colt9]=size(et9); ec9=findstr(g(9,:),'c'); [rowc9 colc9]=size(ec9); eg9=findstr(g(9,:),'g'); [rowg9 colg9]=size(eg9);



50

h9=max([cola9 colt9 colc9 colg9]); if h9==cola9 L9='a'; elseif h9==colt9 L9='t'; elseif h9==colc9 L9='c'; else L9='g'; end ea10=findstr(g(10,:),'a'); [rowa10 cola10]=size(ea10); et10=findstr(g(10,:),'t'); [rowt10 colt10]=size(et10); ec10=findstr(g(10,:),'c'); [rowc10 colc10]=size(ec10); eg10=findstr(g(10,:),'g'); [rowg10 colg10]=size(eg10); h10=max([cola10 colt10 colc10 colg10]); if h10==cola10 L10='a'; elseif h10==colt10 L10='t'; elseif h10==colc10 L10='c'; else L10='g'; end h=h1+h2+h3+h4+h5+h6+h7+h8+h9+h10; konsensus=[L1 L2 L3 L4 L5 L6 L7 L8 L9 L10]; if h>hmax hmax=h; posisi=[pos1 pos2 pos3]; sekuen=konsensus; end end end end fprintf('\n\n\n\n\n sekuen konsensusnya adalah : %s \n', sekuen); fprintf('\n nilai maksimunya = %d \n', hmax); posisi



IDENTIFIKASI SUATU SEKUEN KONSENSUS PADA SEKUEN DNA MENGGUNAKAN PEMROGRAMAN LINIER SKRIPSI DIAN NURHAYATI

Recommend Documents