PENYEJAJARAN BARISAN DNA DENGAN MENGGUNAKAN METODE SIMPUL AKHIR DARI LINTASAN SKOR TERBATAS ERIZKIA MELATI

PENYEJAJARAN BARISAN DNA DENGAN MENGGUNAKAN METODE SIMPUL AKHIR DARI LINTASAN SKOR TERBATAS

ERIZKIA MELATI 0303010133

UNIVERSITAS INDONESIA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM DEPARTEMEN MATEMATIKA DEPOK 2008

Penyejajaran barisan..., Erizkia Melati, FMIPA UI, 2008


Skripsi diajukan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains

Oleh: ERIZKIA MELATI 0303010133

DEPOK 2008


SKRIPSI

:


NAMA

:

ERIZKIA MELATI

NPM

:

0303010133

SKRIPSI INI TELAH DIPERIKSA DAN DISETUJUI DEPOK, 14 Juli 2008

Dra. Siti Aminah, M.Kom

Prof. Dr. Djati Kerami

PEMBIMBING I

Tanggal Lulus Ujian Sidang Sarjana: Penguji I

: Prof. Dr. Djati Kerami

Penguji II

: Dr. Dian Lestari

PEMBIMBING II

Juli 2008

Penguji III : Fevi Novkaniza S.Si., M.Si.


KATA PENGANTAR

Alhamdulillahirobbil’alamin. Segala puji bagi Allah SWT yang telah memberikan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan skripsi ini tepat pada waktunya. Shalawat dan salam kepada Rasulullah Muhammad SAW, untuk keluarganya, sahabatnya, serta pengikutpengikutnya. Skripsi ini takkan dapat diselesaikan tanpa bantuan, dukungan, dan doa dari orang-orang di sekitar penulis. Karena itu, penulis menyampaikan ucapan terima kasih kepada semua pihak yang telah membantu penulis menyelesaikan skripsi ini. Pada kesempatan ini penulis ingin mengucapkan terima kasih kepada: 1. Pak Djati Kerami, selaku pembimbing I, dan Bu Siti Aminah, selaku pembimbing II. Terima kasih untuk semua bimbingannya, nasihat, motivasi, dukungan dan kesabaranya kepada penulis. Mohon maaf jika banyak kesalahan yang telah penulis perbuat. 2. Ibu Bevina, selaku pembimbing akademik, yang telah memberikan arahan, bimbingan, dan nasihat selama masa perkuliahan. 3. Ibu dan Ayah, terima kasih atas semua cinta, pengorbanan, dukungan dan doanya. Tanpa kalian, penulis belum tentu bisa menjadi seperti sekarang ini. Beribu-ribu terima kasih tidak cukup untuk membalas semua pengorbanan yang kalian berikan. Tapi hanya ini yang penulis baru bisa lakukan untuk membalasnya. I love u. i Penyejajaran barisan..., Erizkia Melati, FMIPA UI, 2008

4. Ibu Denny, walau hanya sebentar menjadi pembimbing penulis, penulis ingin mengucapkan terima kasih atas bimbingannya pada awal pengerjaan skripsi ini. 5. Kepada semua dosen Matematika UI yang tak dapat disebutkan satu persatu, terima kasih untuk semua pengorbanan dan ilmu yang diberikan. Ilmu yang kalian berikan tidak ternilai harganya. 6. Semua karyawan Matematika UI, terima kasih untuk bantuannya selama penulis kuliah. Mba Santi, terima kasih atas semua informasi dan bantuannya. 7. Adik tercinta, Resti, yang selalu memberikan semangat kepada penulis. 8. Laras, Hetty, Puput, Rini, Delan, Martin, Inna, Rima, terimakasih banyak atas doa dan dukungannya yang tidak pernah berhenti untuk memberikan semangat. Semuanya itu sangat berarti untuk penulis. Dan teman-teman Math’03 lainnya, terima kasih atas semua bantuan, dukungan, dan kebersamaannya selama penulis kuliah. 9. Teman-teman Math ‘04 dan ‘05 terima kasih atas semua dukungan dan bantuannya selama penulis kuliah. Senang bisa mengenal kalian. 10. Semua keluarga penulis yang telah memberikan dukungan hingga saat ini. 11. Semua pihak yang tidak dapat disebutkan satu persatu, terima kasih tak terhingga.

ii Penyejajaran barisan..., Erizkia Melati, FMIPA UI, 2008

Penulis menyadari bahwa masih terdapat banyak kekurangan di dalam penulisan skripsi ini. Untuk itu, penulis mohon maaf yang sebesarbesarnya. Kritik dan saran yang sifatnya membangun sangat penulis harapkan untuk perbaikan karya penulis selanjutnya. Semoga skripsi ini berguna bagi kita semua. Penulis

Juli 2008

iii Penyejajaran barisan..., Erizkia Melati, FMIPA UI, 2008

DAFTAR ISI

Halaman KATA PENGANTAR

i

ABSTRAK

v

DAFTAR ISI

vii

DAFTAR LAMPIRAN

xi

DAFTAR GAMBAR

xiii

DAFTAR TABEL

xvii

BAB I PENDAHULUAN

1

1.1 Latar Belakang

1

1.2 Permasalahan

3

1.3 Tujuan Penulisan

3

1.4 Pembatasan Masalah

4

1.5 Sistematika Penulisan

4

BAB II KONSEP DASAR PENYEJAJARAN DUA BARISAN DNA

5

2.1 Definisi Penyejajaran Dua Barisan

6

2.2 Konsep Penyejajaran Barisan

6

2.3 Pemberian Skor pada Penyejajaran Dua Barisan DNA

8

2.4 Menentukan Penyejajaran yang Optimum

10

vii


BAB III METODE SIMPUL AKHIR DARI LINTASAN SKOR TERBATAS

13

3.1 Menyajikan Penyejajaran Barisan DNA dalam Graf 3.1.1 Asumsi Graf

13 13

3.1.2 Menggambarkan Graf dari Penyejajaran Dua Barisan DNA

14

3.1.3 Pemberian Nomor pada Simpul

15

3.1.4 Penentuan Bobot dari Tiap Busur

16

3.2 Penyejajaran Dua Barisan DNA Tanpa Daerah Skor yang Rendah

20

3.2.1 Definisi Lintasan X

20

3.2.2 Penjelasan Geometri dari Lintasan X

21

3.3 Metode Simpul Akhir dari Lintasan X

24

3.4 Konsep Pencarian Lintasan yang Optimum dengan Metode Simpul Akhir dari Lintasan X

30

3.4.1 Tahap Inisialisasi

30

3.4.2 Pencarian Simpul-Simpul Akhir dari Lintasan X

30

3.4.3 Pencarian Lintasan X dengan Skor Optimum

32

3.4.4 Penelusuran Kembali

32

3.5 Beberapa Contoh Penyejajaran Dua Barisan DNA dengan Menggunakan Algoritma Simpul Akhir dari Lintasan Skor Terbatas

33 viii


BAB IV HASIL IMPLEMENTASI METODE

75

BAB V PENUTUP

83

DAFTAR PUSTAKA

85

LAMPIRAN

ix


x


DAFTAR LAMPIRAN

Lampiran

Halaman

Lampiran 1 Program

89

xi


xii


DAFTAR GAMBAR

Gambar

Halaman

2.1

Salah satu penyejajaran barisan A dengan barisan B

7

3.1

Penyajian graf untuk penyejajaran dua barisan A dan B

15

3.2

Graf penyejajaran dua barisan DNA ACGG dan AG

19

3.3

Graf untuk mencari lintasan terpanjang dari 0 sampai 12

21

3.4

Metode simpul akhir dari lintasan X

33

3.5 Penyajian graf penyejajaran dua barisan DNA, yaitu ACT dan GT

34

3.6 Penyajian graf penyejajaran dua barisan DNA, yaitu ACT dan GT setelah langkah ke-1

37


39


41


44


47

3.11 Penyajian graf penyejajaran dua barisan DNA, yaitu ACT dan GT setelah langkah ke-6 xiii


49


52


55


57

3.15 Penyajian graf optimum penyejajaran dua barisan DNA, yaitu ACT dan GT

58

3.16 Penyajian graf penyejajaran barisan DNA, yaitu ACT dan GT dengan X = 3, setelah langkah akhir

62

3.17 Penyajian graf penyejajaran barisan DNA, yaitu ACT dan GT dengan X = 1, setelah langkah terakhir

64

3.18 Penyajian graf dari penyejajaran dua barisan, yaitu G C G dan A G C T

65

3.19 Penyajian graf dari penyejajaran dua barisan, yaitu G C G dan A G C T, setelah langkah ke-1

67

3.20 Penyajian graf dari penyejajaran dua barisan, yaitu G C G dan A G C T, setelah langkah ke-2

69

3.21 Penyajian graf optimum dari penyejajaran dua barisan, yaitu G C G dan A G C T

70

4.1 Output penyejajaran barisan pada Contoh 4.1

76


78

xiv



79


81


82

xv


xvi


DAFTAR TABEL

Tabel

Halaman

3.1 Tabel lintasan X yang diperoleh setelah langkah ke-1 penyejajaran barisan ACT dan GT

36


39


41


43


46


48


51


54


xvii


56

3.10 Tabel lintasan X yang diperoleh setelah langkah terakhir penyejajaran barisan ACT dan GT, dengan X = 1

63

3.11 Hasil penyejajaran beberapa contoh barisan dengan menggunakan metode simpul akhir dari lintasan skor terbatas

xviii


72

PENYEJAJARAN BARISAN DNA DENGAN MENGGUNAKAN METODE SIMPUL AKHIR DARI LINTASAN SKOR TERBATAS ERIZKIA MELATI

Recommend Documents