BAB II LANDASAN TEORI. Sebelum beralih kepada permasalahan line digraph, dalam bab ini

BAB II LANDASAN TEORI

Sebelum beralih kepada permasalahan line digraph, dalam bab ini akan dibahas mengenai teori dasar dan definisi yang berhubungan dengan line digraph yang akan digunakan pada Bab III. Akan dibahas juga mengenai metode Sequencing by Hybridization yang merupakan metode untuk membaca suatu barisan DNA yang menggunakan konsep line digraph dalam salah satu tahapannya.

2.1. Pengertian Graf

Suatu graf G = (V,E) merupakan himpunan (V,E) yang mengandung himpunan tak kosong simpul V = V(G) dan himpunan busur E(G) yang menghubungkan dua simpul pada V. Banyaknya simpul pada G dinotasikan dengan |V| sedangkan banyaknya busur dinotasikan dengan |E|. Misalkan e = (u,v) dimana u, v ∈ V dan busur e menghubungkan simpul u dan simpul v, maka u dan v dikatakan saling bertetangga (adjacent). Busur e dikatakan hadir (incident) pada simpul u dan simpul v. Busur yang menghubungkan

6

Sifat-sifat Line..., Juwita Wichapraditha, FMIPA UI, 2008

7

suatu simpul dengan dirinya sendiri disebut gelung (loop). G’ = (V’,E’) dikatakan subgraf dari G = (V,E) jika V ' ⊆ V dan E ' ⊆ E . Suatu simpul pada graf dapat digambarkan sebagai lingkaran kecil atau titik dan busurnya digambarkan sebagai garis yang menghubungkan sembarang dua lingkaran atau titik tadi. Pada Gambar 2.1, diberikan contoh graf dengan lima simpul V = {v1, v2, v3, v4, v5} dan enam busur E = { e1, e2, e3, e4, e5, e6}. Simpul v1 dan v2 dikatakan saling bertetangga karena ada busur e1 yang menghubungkan kedua simpul tersebut, begitu juga dengan simpul v2 dan v3. Busur e1 dikatakan hadir pada simpul v1 dan v2 sedangkan e2 dikatakan hadir pada simpul v2 dan v3. v2 e2

v3 = simpul = busur

e1 v1

e4

e5

e3 v5 e6

v4 Gambar 2.1 Contoh Graf

Graf berarah atau digraph D = (V,A) adalah graf dengan himpunan tak kosong simpul V(D) dengan himpunan busur berarah A(D). Busur berarah a ∈ A dapat direpresentasikan sebagai pasangan terurut (u,v) dimana u, v ∈ V .

Suatu busur (tak berarah) dapat dipandang sebagai busur berarah dengan dua arah. Jika (u, v) ∈ A dengan u, v ∈ V maka simpul u dan simpul v di D bertetangga. Pada graf berarah, busur (u, v) ∈ A digambarkan sebagai garis


8

berarah dari u ke v dengan u disebut titik pangkal dan v disebut titik ujung. Sebuah graf dikatakan memiliki busur sejajar jika terdapat dua atau lebih busur berarah yang memiliki titik pangkal dan titik ujung yang sama. Pengertian subgraf pada graf berarah sama dengan pada graf berarah. Pada Gambar 2.2, diberikan contoh graf berarah dengan empat simpul V = { v1, v2, v3, v4} dan enam busur A = {a1, a2, a3, a4, a5, a6}. Busur a1 menghubungkan simpul v1 dan v2 dimana v1 adalah titik pangkal dan v2 adalah titik ujung. Busur a2 dan a3 adalah busur sejajar karena kedua busur itu memiliki sama – sama titik pangkal v3 dan titik ujung v1. Selanjutnya dalam skripsi ini, busur yang dimaksud adalah busur berarah. a1

v1

a3

a2

v3

v2

a4

a5

a6

v4

Gambar 2.2 Contoh Graf berarah

Sebuah lintasan Pn pada graf G merupakan suatu barisan n simpul dan n - 1 busur v1 , e1 , v2 ,..., vn −1 , en −1 , vn , dimana ei = {vi , vi +1} ∈ E , 1 ≤ i ≤ n − 1 . Panjang dari lintasan didefinisikan sebagai banyaknya busur pada lintasan tersebut. Jika ada busur en yang menghubungkan v1 dengan vn maka lintasan ini disebut tertutup. Lintasan tertutup membentuk suatu lingkaran Cn. Panjang dari lingkaran didefinisikan sebagai banyaknya busur pada lingkaran tersebut. Pada graf berarah, definisi lintasan berarah (dipath) analog dengan


9

definisi lintasan pada graf. Hanya saja ai = (vi , vi +1 ) ∈ A . Jika ada busur berarah an yang menghubungkan vn dengan v1, lintasan berarah tertutup tersebut membentuk lingkaran berarah (dicycle). Sebagai contoh Gambar pada 2.3 (a) adalah lintasan dengan lima simpul (P5) dan panjang lintasan empat, Gambar 2.3 (b) merupakan lingkaran dengan lima simpul (C5) dan panjang lingkaran lima. Untuk lintasan dan lingkaran berarah bisa digambarkan seperti contoh pada Gambar 2.3 (c) dan (d). Sedangkan pada Gambar 2.3 (e) bukan merupakan suatu lintasan karena tidak bisa dibuat suatu barisan dengan lima simpul dan empat busur. Gambar 2.3 (f) juga bukan merupakan suatu lingkaran. v2

v1 v1

e1

v2

e2

v3

e3

v4

e1

e4 v5

v3 e2 e3

e5 e4 (b) v2

v5 (a) v1 v1

a1

v2 a 2

v3 a 3

v4 a 4

a1

v5

v4 v3 a2 a3

a5 a4

v5 (c)

(d) v2

v1 v1

a1

v2 a 2

v3 a 3

v4 a 4

a1

v5

(e)

v3 a2 a3

a5 v5

v4

a4 (f)

v4

Gambar 2.3 (a) Graf lintasan, (b) Graf lingkaran, (c) Graf lintasan berarah, (d) Graf lingkaran berarah, (e) Graf bukan lintasan, (f) Graf bukan lingkaran


10

Lintasan Hamilton adalah lintasan yang mengunjungi setiap simpul pada graf tepat satu kali. Sedangkan jika ada satu simpul yang dikunjungi dua kali dan simpul itu merupakan simpul awal pada lintasan maka lintasan tersebut tertutup dan membentuk lingkaran Hamilton. Lintasan atau lingkaran Hamilton ini belum tentu tunggal. Lintasan Euler adalah lintasan yang mengunjungi setiap busur pada graf tepat satu kali. Sedangkan jika simpul awalnya merupakan simpul akhir pada lintasan maka lintasan tertutup tersebut membentuk lingkaran Euler. Lintasan atau lingkaran Euler ini juga belum tentu tunggal. Ambil contoh pada Gambar 2.1, lintasan Hamiltonnya adalah (v1 , e1 , v2 , e2 , v3 , e4 , v5 , e6 , v4 ) (Gambar 2.4 (a)) sedangkan lintasan Eulernya adalah seperti pada Gambar 2.4(b) (v5 , e3 , v1 , e1 , v2 , e2 , v3 , e4 , v5 , e6 , v4 , e5 , v3 ) . v2 e2

v3

v2 e2

e1 v1

v3

e1 v1

e4

e5

e3

e4

e5

e3 v5 e6

v4

v5 e6

v4

Gambar 2.4 (a) lintasan Hamilton, (b) lintasan Euler

Suatu adjoint G’ dari graf G, adalah suatu graf dimana tiap simpul pada G’ merupakan busur pada G dan dua simpul pada G’ bertetangga jika dan hanya jika busur yang bersesuaian pada graf G memiliki titik akhir yang sama. Sedangkan adjoint D’ dari graf berarah D, merupakan graf berarah


11

dimana tiap simpul pada D’ merupakan busur pada D dan terdapat busur dari simpul u ke v pada D’ jika dan hanya jika titik ujung dari busur u sama dengan titik pangkal busur v pada graf D. Selanjutnya adjoint dari suatu graf ditulis sebagai adjoint saja. Sebagai contoh pada Gambar 2.5 diberikan suatu graf (a) dan adjointnya (b). Graf pada Gambar 2.5(a) memiliki 5 busur sehingga pada adjointnya akan terdapat 5 simpul. Akan ada busur dari simpul e1 ke e2 karena pada graf D titik ujung e1 sama dengan titik pangkal e2 yakni simpul v2. Semua busur akan terbentuk dengan cara yang serupa, sehingga menghasilkan adjoint seperti pada Gambar 2.5 (b).

e2 e3 v3

e1 v1

v2

e2

e3

e1

e4 e5 v4 (a)

v5

e5

e4 (b)

Gambar 2.5 (a) Graf asal D, (b) Adjoint D’

Telah dibahas sebelumnya hubungan antara suatu graf dengan adjoint dimana adjoint dibentuk dari graf yang diketahui. Hal yang sebaliknya juga dapat dilakukan. Jika terdapat suatu adjoint D’ maka graf D dapat dibentuk dengan cara setiap simpul di D’ dijadikan busur pada D dan terbentuk simpul pada D jika busur pada D’ menghubungkan simpul yang berkorespondensi pada busur di D. Graf D ini disebut sebagai graf asal dari D’. Misalkan graf pada Gambar 2.6(a) merupakan suatu adjoint D’, untuk memperoleh graf


12

asal D bentuk semua busur yang berkoresponden dengan simpul di D’. Misalkan untuk busur v1 dan v2 di D, karena simpul v1 dan v2 di D’ terhubung oleh e1 maka akan ada simpul yang merupakan titik ujung v1 dan titik pangkal v2. Lakukan untuk semua busur maka akan terbentuk graf asalnya seperti Gambar 2.6 (b). Pada Gambar 2.6 (a) diperoleh lintasan Hamilton (v1 , e1 , v2 , e2 , v3 , e3 , v5 , e6 , v4 ) sedangkan pada Gambar 2.6 (b) diperoleh lintasan Euler (v1 , v2 , v4 , v3 , v5 ) .

v2 e2

v3 v5

e1 v1

e3

e5

e4

v1

v4

v3

v2 v5 e6 v4 (a)

(b)

Gambar 2.6 (a) Line digraph D’, (b) Graf asal D

Setelah membahas tentang teori graf, selanjutnya akan dibahas suatu metode yang dapat digunakan untuk mengenali barisan dari suatu untai DNA. Salah satu tahapan pada metode ini menggunakan teori graf sebagai alat bantu.


13

2.2. Sequencing by Hybridization

Tubuh makhluk hidup tersusun atas molekul – molekul DNA. DNA adalah asam nukleat yang mengandung materi genetik dan berfungsi untuk mengatur perkembangan biologis seluruh bentuk kehidupan secara seluler. Suatu rantai DNA tersusun atas fosfat, gula dan 3 x 109 pasang nukleotida. Nukleotida atau basa nitrogen terdiri dari adenine (A), guanine (G), timin (T), dan cytosin (C). Jika dilihat di bawah mikroskop, molekul DNA terlihat seperti dua pita yang terangkai (double helix) yang dihubungkan oleh suatu ikatan hidrogen. Saat DNA dipanaskan, ikatan hidrogen ini akan hilang dan menyisakan dua pita tunggal. Satu pita tunggal dibentuk oleh barisan nukleotida. Barisan nukleotida tidak mudah dikenali. Dibutuhkan suatu proses untuk mengenali suatu barisan nukleotida dari suatu DNA atau disebut dengan barisan DNA, salah satunya adalah dengan metode Sequencing by Hybridization (SBH). Metode ini pertama kali diperkenalkan pada tahun 1988 [Pev01]. Metode SBH ini terbagi menjadi dua tahapan, tahapan biokimia dan tahapan komputasional. Pada tahapan biokimia, DNA akan diolah secara biokimia. Pengolahan ini akan menghasilkan fragmen – fragmen pendek berukuran tertentu yang disebut dengan oligonukleotida. Himpunan semua oligonukleotida ini disebut dengan spektrum. Diberikan suatu DNA yang belum diketahui. DNA ini direpresentasikan dalam array berukuran l yang


14

terkandung pada barisan DNA, namun urutannya belum diketahui pada barisan tesebut. Untuk sebuah barisan s dengan panjang n, terdapat sebanyak n – l +1 oligonukleotida dengan panjang l karena untuk barisan dengan panjang n jika dibentuk suatu fragmen pendek dengan panjang l dimana barisannya harus berurut maka akan ada sebanyak n – l fragmen ditambah dengan satu fragmen dengan panjang l yang terakhir. Sehingga banyaknya elemen di spektrum adalah n – l +1 dengan kondisi bahwa tidak ada oligonukleotida yang muncul lebih dari sekali dalam barisan. Pada tahapan komputasional, array dari fragmen – fragmen pendek ini digunakan untuk membaca barisan DNA secara utuh. Terdapat beberapa metode untuk membaca barisan yang terbentuk. Di antaranya dengan menggunakan metode SSP (Shortest Superstring Problem) yakni suatu masalah dimana jika diberikan sekumpulan untai s1, s2, .., sn, rangkai untai – untai tersebut sehingga menghasilkan satu untai s yang mengandung s1, s2, .., sn sebagai subuntai, sedemikian sehingga panjang dari s minimum. Selain itu, juga dapat digunakan metode TSP (Traveling Salesman Problem) yakni dengan mendefinisikan overlap (si, sj) sebagai panjang dari bagian paling kanan si yang sama dengan bagian paling kiri sj, bentuk graf dengan n simpul yang mewakili n untai s1, s2, .., sn dan busurnya adalah overlap (si, sj) antara simpul si dan simpul sj dan solusinya adalah jarak terpendek untuk mengunjungi tiap simpul tepat satu kali. Cara lain adalah dengan menggunakan lintasan Hamilton atau Euler seperti yang akan digunakan dalam skripsi ini.


15

Pada skripsi ini akan digunakan bantuan teori graf untuk mendapatkan barisan DNA yang utuh. Untuk dapat melakukan hal itu, akan dibentuk suatu graf dengan simpul sebanyak elemen pada spektrum dan busur berarah yang menghubungkan antar dua simpul dibentuk dengan aturan tertentu. Graf tersebut disebut graf DNA. Pembentukan simpul dan busur ditetapkan sedemikian rupa sehingga kemungkinan rangkaian DNA yang utuh dapat diperoleh dengan mencari lintasan Hamilton pada graf tersebut. Oleh karena itu, masalah mencari barisan DNA dari spektrum dimodelkan menjadi masalah mencari lintasan Hamilton pada graf DNA.

2.3. Pembentukan Graf DNA

Graf DNA adalah suatu graf berarah, sebut graf H dengan simpul menyatakan spektrum. Sedangkan untuk busurnya, terdapat busur antara dua simpul, dari x ke y jika k-1 nukleotida paling kanan dari simpul x sama dengan k-1 nukleotida paling kiri dari y, dengan k menyatakan panjang spektrum. Graf yang terbentuk adalah graf yang keterhubungan antar simpulnya tidak banyak karena aturan pembentukan busur tadi. Untuk spektrum dengan panjang 3 {TCA, CAC, ACA, CAG, AGG} yang diperoleh pada tahapan biokimia, spektrum tersebut akan menjadi simpul pada graf H (Gambar 2.7(a)). Untuk pembentukan busurnya, perhatikan simpul TCA dan CAC karena 2 nukleotida paling kanan dari TCA


16

sama dengan 2 nukleotida paling kiri dari CAC yakni CA maka terbentuk busur yang menghubungkan TCA ke CAC. Perhatikan juga simpul CAG dan AGG karena 2 nukleotida paling kanan dari CAG sama dengan 2 nukleotida paling kiri dari AGG yakni AG maka terbentuk busur yang menghubungkan CAG ke AGG, semua busur dibentuk dengan cara yang serupa sehingga graf H yang terbentuk akan seperti pada Gambar 2.7(b). Barisan DNA dapat dibentuk dengan mencari lintasan hamilton pada graf H, pada contoh 2.7(b) lintasan Hamilton yang terbentuk adalah TCA-CAC-ACA-CAG-AGG sehingga barisan DNA yang terbentuk adalah TCACAGG.

CAC

ACA

CAC

ACA TCA

TCA CAG

AGG

CAG

(a)

AGG (b)

Gambar 2.7 (a) Simpul pada graf DNA, (b) Contoh graf DNA

Namun pencarian lintasan Hamilton membutuhkan waktu ekponensial. Dari analisis algoritma diketahui bahwa waktu pencarian lintasan Euler adalah polinomial. Untuk mengurangi kompleksitas pencarian barisan DNA yang utuh dari eksponensial ke polinomial, graf H dapat ditransformasikan menjadi graf baru, sebut saja graf G, dimana graf H adalah line digraph dari graf G tersebut. Graf G disebut sebagai graf asal dari H.


17

Proses pembentukan graf berarah G dari graf berarah H adalah sebagai berikut, tiap simpul pada graf H menjadi busur pada graf G (jadi busur pada graf G berkorespondensi dengan spektrum). Busur ini menghubungkan simpul dengan label k-1 paling kiri dan k-1 paling kanan nukleotida dari oligonukleotida yang bersesuaian dengan busurnya. Misalkan untuk graf DNA H pada Gambar 2.7(b), simpul pada graf H akan menjadi busur pada graf G (Gambar 2.8 (a)). Busur – busur yang terbentuk akan menghubungkan simpul dengan label 2 nukleotida paling kiri dan 2 nukleotida paling kanan dari busur tersebut. Misalkan untuk busur CAG, busur ini akan menghubungkan simpul CA dan simpul AG. Seterusnya pembentukan simpul ini berlaku untuk tiap busur. Graf G yang terbentuk akan seperti pada Gambar 2.8(b).

TCA

CAC

TCA

TC

CAC

CA ACA

ACA CAG

AC

CAG

AGG

(a)

AG

AGG

GG

(b)

Gambar 2.8 (a) Busur pada graf asal, (b) Graf asal dari graf DNA pada Gambar 2.7(a)

Dari graf G pada Gambar 2.8(b), lintasan Euler yang diperoleh juga TCA-CAC-ACA-CAG-AGG sama dengan lintasan Hamilton yang diperoleh


18

dari graf H pada Gambar 2.7(b) sehingga akan terbentuk barisan DNA yang sama, yakni TCACAGG . Graf DNA merupakan suatu line digraph sehingga permasalahannya adalah bagaimana mengenali suatu line digraph dan merubahnya menjadi graf asalnya dengan kompleksitas polinomial sehingga mencari barisan DNA yang utuh dapat dilakukan dalam waktu polinomial. Untuk itu perlu dipelajari sifat – sifat pada line digraph sehingga dapat ditentukan kompleksitas dari transformasinya lewat sifat – sifat ini. Namun dalam skripsi ini yang dibahas hanya mengenai sifat – sifat line digraph yang berlaku secara umum pada sembarang graf serta cara untuk mengenali line digraph dan membentuk graf asalnya saja, tidak sampai membahas solusi dari masalah pencarian barisan DNA secara utuh.


BAB II LANDASAN TEORI. Sebelum beralih kepada permasalahan line digraph, dalam bab ini

Recommend Documents