4 bab ii teori graf merupakan pokok bahasan yang sudah tua ...repository.ump.ac.id/641/3/bab ii_ari...
TRANSCRIPT
4
BAB II
LANDASAN TEORI
A. Graf
Teori graf merupakan pokok bahasan yang sudah tua usianya namun
memiliki banyak terapan sampai saat ini. Graf digunakan untuk
merepresentasikan objek-objek diskrit dan hubungan antara objek-objek
tersebut. Representasi visual dari graf adalah dengan menyatakan objek yang
dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara
objek dinyatakan dengan garis (Munir. 2007: 353).
1. Definisi graf
Secara matematis, graf G didefinisikan sebagai pasangan himpunan
(V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah
himpunan tak kosong dari simpul-simpul (vertices atau node) dan E adalah
himpunan sisi (edge atau arcs) yang menghubungkan sepasang simpul.
Dengan demikian bahwa V tidak boleh kosong sedangkan E boleh kosong,
sehingga sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun,
tetapi simpulnya harus ada minimal satu (Munir. 2007: 357).
4
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
5
2. Jenis-jenis graf
Graf dapat digolongkan menjadi beberapa jenis graf yang spesifik.
Jenis-jenis graf ini akan dijelaskan seperlunya untuk membatasi graf dan
menyamakan pengertian mengenai graf yang akan dipakai dan dibahas
pada penelitian ini.
Graf dapat dikelompokan menjadi beberapa kategori (jenis)
bergantung pada sudut pandang pengelompokannya. Pengelompokan graf
dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang,
berdasarkan orientasi arah pada sisi atau berdasarkan jumlah simpul.
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf,
maka secara umum graf dapat digolongkan menjadi dua jenis yaitu:
a. Graf sederhana
Graf sederhana adalah graf yang tidak mengandung gelang
maupun sisi ganda. Pada graf sederhana, sisi adalah pasangan tak-
terturut (unordered pairs). Jadi menuliskan sisi (u,v) sama saja dengan
(v,u). Dapat didefinisikan juga bahwa graf sederahana G = (V, E)
terdiri dari himpunan tak kosong simpul-simpul dan E adalah
himpunan pasangan tak-berurut yang berbeda yang disebut sisi.
Contoh graf sederhana:
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
6
Gambar 1. Graf sederhana
b. Graf tidak sederhana
Graf tak sederhana adalah graf yang mengandung sisi ganda atau
gelang. Ada dua macam graf tak sederhana yaitu graf ganda
(multigraph) dan graf semu (pseudograph). Graf ganda adalah graf
yang mengandung sisi ganda. Sisi ganda yang menghubungkan
sepasang simpul bisa lebih dari dua buah. Dapat juga didefinisikan,
graf ganda G = (V, E) terdiri dari himpunan tak kosong simpul-simpul
dan E adalah himpunan ganda (multiset) yang mengandung sisi ganda.
Contoh graf tak sederhana:
Gambar 2. Graf ganda
Sedangkan graf semu adalah graf yang mengandung gelang (loop).
Graf semu lebih umum daripada graf ganda, karena sisi pada graf
2 3
4
1
1
2 3
4
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
7
semu dapat terhubung ke dirinya sendiri. Contoh graf semu dengan e
adalah simbol edge atau busur;
Gambar 3. Graf semu
Sisi pada graf mempunyai orientasi arah. Berdasarkan orientasi arah
pada sisi, maka secara umum graf dibedakan atas dua jenis, yaitu:
a. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf
tak-berarah. Pada graf tak berarah, urutan pasangan simpul yang
dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah
sisi yang sama.
Contoh graf tak berarah.
Gambar 4. Graf tak berarah
b. Graf berarah (direct graph atau digraph)
Graf yang tiap sisinya diberikan orientasi arah disebut sebagai graf
berarah. Sisi berarah dapat disebut busur (arc). Pada graf berarah, (u,
1
2
4
3
e 1 e 3e 4
e5e 7
e 8
3
1
4
2
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
8
v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata
lain (u,v) ≠ (v,u). Simpul u dinamakan simpul asal (initial vertex) dan
simpul v dinamakan simpul terminal (terminal vertex) (Munir. 2007).
Sebuah graf berarah G terdiri dari:
i. Sebuah himpunan V = V(G) yang elemen-elemennya disebut
vertex, titik atau node.
ii. Suatu koleksi E = E(G) dari pasangan-pasangan vertex terurut yang
disebut busur atau edge berarah.
Dinotasikan G (V, E) bilamana ingin menegaskan dua bagian dari
G (Lipschuts. 2002: 97).
Definisi graf dapat diperluas sehingga mencakup graf ganda
berarah (directed multigraph). Pada graf ganda berarah, gelang dan
sisi ganda diperbolehkan ada (Munir. 2007).
Gambar 5. Graf berarah
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf
dapat digolongkan menjadi dua jenis:
a. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya mencapai n
berhingga. Sebuah graf berarah G yang dinotasikan G (V, E)
3
1
4
2
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
9
dikatakan berhingga jika himpunan V dari verteks-verteksnya dan
himpunan E dari busurnya (edge berarahnya) berhingga (Lipschuts.
2002: 97). Salah satu contoh graf berhingga antara lain pada Gambar 2
berupa graf ganda dimana jumlah simpulnya berhingga.
b. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya n tidak berhingga banyaknya disebut
graf tak-berhingga.
3. Terminologi dasar
a. Bertetangga (Adjacent)
Pada graf berarah, sisi di (u, v) adalah busur maka u dikatakan
bertetangga dengan v dan v dikatakan tetangga dari u. Pada Gambar 5,
simpul 1 bertetangga dengan simpul 2 dan simpul 2 dikatakan
tetangga dari simpul 1.
b. Bersisian
Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan
simpul u dan simpul v. Pada Gambar 1, sisi (2, 3) bersisian dengan
simpul 2 dan simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan
simpul 4, tetapi sisi (1, 2) tidak bersisian dengan simpul 4.
c. Graf kosong (Null graph atau Empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong disebut
grag kosong dan ditulis sebagi Nn yang dalam hal ini n adalah jumlah
simpul. Contoh graf kosong seperti di bawah ini:
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
10
Gambar 6. Graf kosong N5
d. Derajat (Degree)
Pada graf berarah, derajat suatu simpul dibedakan menjadi dua
macam untuk mencerminkan jumlah busur dengan simpul tersebut
sebagai simpul asal dan jumlah busur dengan simpul tersebut sebagai
simpul terminal. Simpul yang berderajat satu disebut anting-anting
(pendant vertex). Pada Gambar 6, d(4) = 1, karena itu simpul 4 adalah
anting-anting.
Derajat siatu simpul pada graf berarah dinyatakan dengan din (v)
dan dout (v) yang dalam hal ini,
din (v) = derajat-masuk (in-dergee) = jumlah busur yang masuk ke
simpul v, sedangkan
dout (v) = derajat-keluar (out-dergee) = jumlah busur yang keluar dari
simpul v. Dan d(v) = din (v) + dout (v).
Dan sisi gelang pada graf berarah menyumbangkan 1 untuk
derajat-masuk dan satu untuk derajat-keluar. Contoh pada Gambar 5,
dapat diketahui:
1
2
3
4 5
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
11
din (1) = 2; dout (1) = 1
din (2) = 2; dout (2) = 3
din (3) = 1; dout (3) = 2
din (4) = 2; dout (4) = 1
Pada graf berarah G = (V, E) selalu berlaku hubungan
∑ ∑∈ ∈
==Vv Vv
outin EVdVd )()(
sehingga untuk contoh tersebut,
∑ ∑∈ ∈
==+++===+++=Vv Vv
outin EVdVd 71231)(72122)(
e. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan
vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan
sisi-sisi yang berbentuk vo, e1, v1, e2,,,, vn-1, en, vn sedemikian sehingga
e1 = (vo, v1,), e2 = (v1, v2,),,,, en = (vn-1, vn,) adalah sisi-sisi dari graf G.
Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Dan
sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua
simpulnya berbeda (setiap sisi yang dilalui hanya satu kali). Lintasan
yang berawal dan berakhir pada simpul yang sama disebut lintasan
tertutup (closed path), sedangkan lintasan yang tidak berawal dan
berakhir pada simpul yang sama disebut lintasan terbuka (open path).
Contoh pada Gambar 1,
lintasan 1, 2, 4, 3 adalah lintasan sederhana, juga lintasan terbuka;
lintasan 1, 2, 4, 3, 1 adalah lintasan sederhana, juga lintasan tertutup;
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
12
lintasan 1, 2, 4, 3, 2 bukan merupakan lintasan sederhana, tetapi
termasuk lintasan terbuka.
Panjang lintasan adalah jumlah sisi pada lintasan tersebut.
Lintasan 1, 2, 4, 3 pada Gambar 1 memiliki panjang lintasan 3.
f. Siklus (Cycle) atau sirkuit (circuit)
Sirkuit atau siklus adalah lintasan yang berawal dan berakhir pada
simpul yang sama. Panjang sirkuit adalah jumlah sisi yang ada di
dalam sirkuit tersebut. Sebuah sirkuit dikatakan sirkuit sederhana
(simple circuit) jika setiap sisi yang dilalui berbeda. Contoh pada
Gambar 1, sirkuit sederhana ditunjukan oleh 1, 2, 3, 1, sedangkan 1, 2,
4, 3, 2, 1 bukan merupakan sirkuit sederhana, karena sisi (1, 2) dilalui
dua kali.
g. Terhubung (Connected)
Keterhubungan dua buah simpul adalah penting dalam graf. Dua
buah simpul u dan simpul v dikatakan terhubung jika terdapat lintasan
dari u ke v. Jika dua buah simpul terhubung maka pasti simpul yang
pertama dapat dicapai dari simpul yang kedua (Munir. 2007). Suatu
graf G dikatakan terhubung bila untuk setiap pasang simpul misalkan
vi dan vj di dalam himpunan V terdapat lintasan dari vi ke vj
(Lipschutz. 2002).
Jika setiap pasang simpul di dalam graf terhubung, maka graf
tersebut dapat dikatakan graf terhubung atau dengan kata lain graf tak
berarah G disebut graf terhubung (connected graph) jika untuk setiap
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
13
simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v
(yang juga harus berarti ada lintasan dari u ke v). Jika tidak, maka G
disebut graf tak-terhubung (disconnected graph) (Munir. 2007: 371).
Pada Gambar 1 merupakan contoh graf terhubung, sedang untuk
contoh graf tak-terhubung antara lain:
Gambar 7. Graf tak-terhubung
Graf yang hanya terdiri atas satu simpul saja (tidak ada sisi) tetap
dikatakan terhubung, karena simpul tunggalnya terhubung dengan
dirinya sendiri. Pada graf berarah G dikatakan terhubung jika graf tak
berarahnya terhubung (graf tak berarah dari G diperoleh dengan
menghilangkan arahnya). Keterhubungan dua buah simpul pada graf
berarah dibedakan menjadi terhubung kuat dan terhubung lemah.
Dua simpul, u dan v pada graf berarah G disebut terhubung kuat
(strongly connected) jika terdapat lintasan berarah dari u ke v dan juga
sebaliknya lintasan berarah dari v ke u. Pada Gambar 8 (a), simpul 1
dan simpul 3 terhubung kuat karena terdapat lintasan dari 1 ke 3 (yaitu
1, 2, 3), begitu jug terdapat lintasan dari 3 ke 1 (yaitu 3, 4, 5, 1).
1
2 3
4 5
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
14
Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tak
berarahnya, maka u dan v dikatakan terhubung lemah (weakly
connected). Pada Gambar 8 (b), simpul 1 dan simpul 3 terhubung
lemah karena hanya terdapat lintasan dari 3 ke 1 (yaitu 3, 5, 4, 1),
tetapi tidak ada lintasan dari 1 ke 3 (Munir. 2007: 372).
(a) (b)
Gambar 8. (a) Graf terhubung kuat, (b) Graf terhubung lemah
4. Lintasan dan Sirkuit Euler
Lintasan Euler adalah lintasan yang melalui setiap sisi di dalam graf
tepat satu kali. Bila lintasan tersebut kembali ke simpul asal, membentuk
lintasan tertutup (sirkuit), maka lintasan tertutup tersebut dinamakan
sirkuit Euler. Maka sirkuit Euler adalah sirkuit yang melewati masing-
masing sisi tepat satu kali.
Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian
graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi
Euler (semi-Eulerian graph).
5
4 3
2
1
5
4 3
2
1
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
15
Syarat cukup dan perlu mengenai keberadaan lintasan Euler maupun
sirkuit Euler di dalam suatu graf ternyata sangat sederhana. Euler
menemukan syarat tersebut ketika memecahkan masalah jembatan
Konigsberg. Graf yang memiliki sirkuit Euler pasti mempunyai lintasan
Euler, tetapi tidak sebaliknya.
Lintasan dan sirkuit Euler juga terdapat pada graf berarah. Teorema
yang menyatakan syarat keberadaan lintasan dan sirkuit Euler pada graf
berarah dinyatakan dengan teorema berikut:
“Graf terhubung berarah G memiliki sirkuit Euler jika dan hanya jika G
terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar
sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan tiap
simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua
simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-
masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari
derajat-keluar”.
(Munir. 2007: 404 -
406)
Contoh graf yang menggambarkan lintasan dan sirkuit Euler.
Graf (a) Graf (b)
1
2 3
4
1
2 3
4
7
6
5
a b
cde
a
b c de
fg h
ijk
l
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
16
Gambar 9. Graf yang memiliki lintasan Euler dan Sirkuit Euler
Contoh lintasan Euler pada graf (a) adalah c, b, a, e, d.
Contoh sirkuit Euler pada graf (b) adalah a, d, j, l, k, I, h, g, f, e, c, b.
B. Rantai RNA (Ribonucleic acid)
1. Pengertian RNA
RNA merupakan singkatan dari Ribonucleic acid atau asam
ribonukleat. RNA dibentuk oleh DNA (Deoxyribonucleic acid) melalui
proses transkripsi (Syamsuri. 2004: 66). RNA merupakan rantai tunggal
polinukleotida (Aryulina. 2005: 66).
RNA adalah suatu polimer asam nukleotida dari empat ribonukleotida.
Tiap ribonukleotida terdiri dari gula pentose (D-ribose), molekul gugusan
pospat dan sebuah basa nitrogen (Suryo. 1994: 78).
Ada tiga macam RNA, yaitu RNA duta (RNA-d) atau RNA
messenger (mRNA), RNA ribosom (RNA-r) dan RNA transfer (RNA-t).
Semua RNA tersebut dihasilkan oleh DNA melalui proses transkripsi.
Sifat RNA adalah mudah terurai sehingga sel akan terus memproduksinya
(Sartini Bayu. 2008). Pada penelitian ini, rantai RNA yang dibahas adalah
jenis RNA duta (RNA-d) atau RNA messenger (mRNA).
2. Struktur RNA dan perbedaannya dengan DNA
Pada makhluk hidup tertentu, RNA-lah merupakan molekul genetika
keseluruhannya dan membawa segala pertanggung jawaban seperti yang
dimiliki DNA. Bentuk dari RNA adalah rantai tunggal yang ditempati oleh
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
17
gula ribosa, fosfat dan basa. Basa purin RNA terdiri dari Adenin (A) dan
Guanin (G), sedangkan basa pirimidin terdiri dari Sitosin (C) dan Urasil
(U) (Syamsuri. 2004).
Purin dan pirimidin yang berikatan dengan ribose membentuk suatu
molekul yang dinamakan ribonukleosida. RNA merupakan hasil
transkripsi dari DNA, sehingga RNA merupakan polimer yang jauh lebih
pendek dibanding DNA (Aryulina. 2005: 67).
Perbedaan antara RNA dengan DNA antara lain:
a. Mengenai ukuran dan bentuk
Pada umumnya molekul RNA lebih pendek daripada molekul
DNA. DNA terbentuk double helix (rantai ganda) dan merupakan
rantai panjang sedangkan RNA berbentuk single strand (rantai
tunggal) dan merupakan rantai pendek.
b. Mengenai susunan kimia
Molekul RNA juga merupakan polimer nukleotida, perbedaannya
dengan DNA antara lain: (1). Gula yang menyusun RNA bukan
dioksiribosa, melainkan ribose. (2). Basa pirimidin yang menyusun
RNA bukan timin melainkan Urasil (U), sedangkan basa purin antara
keduanya sama yakni Adenin (A) dan Guanin (G).
c. Mengenai Lokasinya
DNA umumnya terdapat di dalam nukleus dan ada pula yang
terdapat pada kloroplas dan mitokondria, sedangkan terdapatnya RNA
tergantung dari macamnya, yaitu:
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
18
1) RNA duta (RNAd), nama asingnya messenger RNA (mRNA)
terdapat dalam nukleus. RNAd dicetak oleh salah satu pita DNA
yang berlangsung di dalam nukleus.
2) RNA pemindah (RNAp), nama asingnya transfer RNA (tRNA),
terdapat di dalam sitoplasma.
3) RNA ribosom (RNAr), nama asingnya ribosome RNA (rRNA),
terdapat terutama di ribosoma. Molekulnya berupa pita tunggal,
tidak bercabang.
d. Mengenai fungsinya
DNA berfungsi memberi informasi/keterangan genetika,
sedangkan fungsi RNA umumnya adalah membawa pertangggung
jawaban atas informasi/keterangan genetika.
(Suryo. 1994)
3. G-Enzyme dan U, C-Enzyme
Sesuatu yang digunakan untuk memotong baik itu rantai RNA
maupun DNA adalah enzim. Enzim adalah katalisator di dalam sel
makhluk hidup (Syamsuri. 2004: 26). Enzim lengkap yang dimaksudkan
dalam rekonstruksi rantai RNA adalah enzim-enzim yang memutus mata
rantai dari sebuah rantai RNA.
Seperti yang sudah diketahui bahwa rantai RNA tersusun atas basa
purin dan basa pirimidin yaitu Adenin (A), Guanin (G), Sitosin (C) dan
Urasil (U). Pada kenyataannya, terdapat dua jenis enzim yang memutus
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
19
mata rantai RNA. Yang pertama disebut G-Enzyme. G-Enzyme ini berguna
untuk memutus rantai RNA tiap setelah mata rantai G dalam rantai RNA.
G-Enzyme ini akan memutus rantai RNA menjadi bagian-bagian yang
disebut dengan G-fragment. Sebagai contoh, salah satu rantai RNA
sebagai berikut:
UCGAGCUAGCGAAG
G-Enzyme akan memutusnya sehingga menjadi fragmen-fragmen yang
disebut G-fragment berupa UCG, AG, CUAG, CG, AAG.
Gambar 10. Proses pembentukan G-fragment
Enzim yang kedua disebut U, C-Enzyme. Enzim ini berguna untuk
memutus mata rantai RNA sedemikian sehingga rantai RNA tersebut akan
diputus menjadi fragmen-fragmen setiap setelah mata rantai U dan setiap
setelah mata rantai C. U, C-Enzyme ini akan memutus mata rantai RNA
menjadi bagian-bagian yang disebut dengan U, C-fragment. Sebagai
contoh untuk rantai RNA di atas, U, C-Enzyme akan memutusnya menjadi
fragmen-fragmen berupa U, C, GAGC, U, AGC, GAAG.
UCGAGCUAGCGAAG
G-Enzyme
UCG AG CUAG CG AAG
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
20
Gambar 11. Proses pembentukan U, C-fragment
C. Rekonstruksi Rantai RNA
Rekonstruksi adalah penyusunan ulang atau pembangunan kembali
sesuatu yang sudah ada. Sehingga dapat didefinisikan rekonstruksi rantai RNA
adalah penyusunan ulang atau pembangunan kembali rantai RNA yang
terputus.
Metode rekonstruksi rantai RNA yang dulu digunakan adalah cara
acak/manual yaitu dengan mencoba segala kemungkinan penyusunan yang
mungkin dapat dilakukan dari fragmen-fragmen yang diketahui tersebut.
Metode acak ini akan menghasilkan n! kemungkinan rantai RNA yang dicari,
dengan n adalah jumlah fragmen dari rantai RNA yang diketahui (Noorzaman.
2008). Untuk menentukan satu rantai RNA dari sekian kemungkinan rantai
RNA yang terjadi membutuhkan waktu yang cukup lama karena harus
mendefinisi dari sekian n! kemungkinan rantai RNA yang terjadi. Sebagai
contoh, diberikan beberapa G-fragment dan U, C-fragment berikut:
G-fragment : AG, UCG, CUAG, AAG, CG
U, C-fragment : U, C, GAGC, U, AGC, GAAG
UCGAGCUAGCGAAG
U,C-Enzyme
GAGC U AGC GAAG C U
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
21
Perlu diketahui dalam metode rekonstruksi cara acak/manual,
kedudukan antar fragmen dalam susunan fragmen adalah berbeda atau tidak
sama karena urutan di sini sangat diperhatikan karena akan berhubungan
dengan susunan/urutan basa pada rantai RNA yang nantinya akan memiliki
arti kode genetik yang berbeda pula. Misalnya: AG, UCG, CUAG, AAG, CG
≠ AG, UCG, AAG, CUAG, CG ≠ AAG, UCG, CUAG, AG, CG dan bentuk
lainnya.
Langkah pertama dalam metode rekonstruksi cara acak/manual adalah
membuat n! dari salah satu fragmen dan diusahakan yang mempunyai jumlah
fragmen yang lebih sedikit sehingga meminimalkan penyusunan
kemungkinan. Langkah kedua adalah menyusun kemungkinan rantai RNA
dari sekian banyak n! tersebut. Langkah terakhir adalah menemukan atau
menentukan kemungkinan rantai RNA yang terjadi yang apabila dipecah
dengan enzim yang lainnya akan menghasilkan fragmen yang sama dengan
fragmen dari enzim yang satunya yang sudah diketahui.
Sebagai contoh untuk fragmen di atas adalah sebagai berikut:
1. Membuat n! dari salah satu fragmen yang diketahui yang mempunyai
jumlah fragmen lebih sedikit, yakni G-fragment yang memiliki 5 buah
fragmen yang jauh lebih sedikit dibanding U, C-fragment. Maka akan
terdapat n! = 5! = 5 X 4 X 3 X 2 X 1 = 120 buah kemungkinan rantai
RNA.
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
22
2. Menyusun kemungkinan rantai RNA yang terjadi sebanyak n! atau 120
rantai yang membangun himpunan dari fragmen yang lain. Maka diperoleh
kemungkinan sebagai berikut:
1) AGUCGCUAGAAGCG
2) AGUCGCUAGCGAAG
3) AGUCGAAGCUAGCG
4) AGUCGAAGCGCUAG
5) AGUCGCGCUAGAAG
6) AGUCGCGAAGCUAG
7) AGCUAGUCGAAGCG
8) AGCUAGUCGCGAAG
9) AGCUAGAAGUCGCG
10) AGCUAGAAGCGUCG
11) AGCUAGCGUCGAAG
12) AGCUAGCGAAGUCG
13) AGAAGUCGCUAGCG
14) AGAAGUCGCGCUAG
15) AGAAGCUAGUCGCG
16) AGAAGCUAGCGUCG
17) AGAAGCGUCGCUAG
18) AGAAGCGCUAGUCG
19) AGCGUCGCUAGAAG
20) AGCGUCGAAGCUAG
21) AGCGCUAGUCGAAG
22) AGCGCUAGAAGUCG
23) AGCGAAGUCGCUAG
24) AGCGAAGCUAGUCG
25) UCGAGCUAGAAGCG
26) UCGAGCUAGCGAAG
27) UCGAGAAGCUAGCG
28) UCGAGAAGCGCUAG
29) UCGAGCGCUAGAAG
30) UCGAGCGAAGCUAG
31) UCGCUAGAGAAGCG
32) UCGCUAGAGCGAAG
33) UCGCUAGAAGAGCG
34) UCGCUAGAAGCGAG
35) UCGCUAGCGAGAAG
36) UCGCUAGCGAAGAG
37) UCGAAGAGCUAGCG
38) UCGAAGAGCGCUAG
39) UCGAAGCUAGAGCG
40) UCGAAGCUAGCGAG
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
25
41) UCGAAGCGAGCUAG
42) UCGAAGCGCUAGAG
43) UCGCGAGCUAGAAG
44) UCGCGAGAAGCUAG
45) UCGCGCUAGAGAAG
46) UCGCGCUAGAAGAG
47) UCGCGAAGAGCUAG
48) UCGCGAAGCUAGAG
49) CUAGAGUCGAAGCG
50) CUAGAGUCGCGAAG
51) CUAGAGAAGUCGCG
52) CUAGAGAAGCGUCG
53) CUAGAGCGUCGAAG
54) CUAGAGCGAAGUCG
55) CUAGUCGAGAAGCG
56) CUAGUCGAGCGAAG
57) CUAGUCGAAGAGCG
58) CUAGUCGAAGCGAG
59) CUAGUCGCGAGAAG
60) CUAGUCGCGAAGAG
61) CUAGAAGAGUCGCG
62) CUAGAAGAGCGUCG
63) CUAGAAGUCGAGCG
64) CUAGAAGUCGCGAG
65) CUAGAAGCGAGUCG
66) CUAGAAGCGUCGAG
67) CUAGCGAGUCGAAG
68) CUAGCGAGAAGUCG
69) CUAGCGUCGAGAAG
70) CUAGCGUCGAAGAG
71) CUAGCGAAGAGUCG
72) CUAGCGAAGUCGAG
73) AAGAGUCGCUAGCG
74) AAGAGUCGCGCUAG
75) AAGAGCUAGUCGCG
76) AAGAGCUAGCGUCG
77) AAGAGCGUCGCUAG
78) AAGAGCGCUAGUCG
79) AAGUCGAGCUAGCG
80) AAGUCGAGCGCUAG
81) AAGUCGCUAGAGCG
82) AAGUCGCUAGCGAG
83) AAGUCGCGAGCUAG
84) AAGUCGCGCUAGAG
85) AAGCUAGAGUCGCG
86) AAGCUAGAGCGUCG
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
26
87) AAGCUAGUCGAGCG
88) AAGCUAGUCGCGAG
89) AAGCUAGCGAGUCG
90) AAGCUAGCGUCGAG
91) AAGCGAGUCGCUAG
92) AAGCGAGCUAGUCG
93) AAGCGUCGAGCUAG
94) AAGCGUCGCUAGAG
95) AAGCGCUAGAGUCG
96) AAGCGCUAGUCGAG
97) CGAGUCGCUAGAAG
98) CGAGUCGAAGCUAG
99) CGAGCUAGUCGAAG
100) CGAGCUAGAAGUCG
101) CGAGAAGUCGCUAG
102) CGAGAAGCUAGUCG
103) CGUCGAGCUAGAAG
104) CGUCGAGAAGCUAG
105) CGUCGCUAGAGAAG
106) CGUCGCUAGAAGAG
107) CGUCGAAGAGCUAG
108) CGUCGAAGCUAGAG
109) CGCUAGAGUCGAAG
110) CGCUAGAGAAGUCG
111) CGCUAGUCGAGAAG
112) CGCUAGUCGAAGAG
113) CGCUAGAAGAGUCG
114) CGCUAGAAGUCGAG
115) CGAAGAGUCGCUAG
116) CGAAGAGCUAGUCG
117) CGAAGUCGAGCUAG
118) CGAAGUCGCUAGAG
119) CGAAGCUAGAGUCG
120) CGAAGCUAGUCGAG
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010
48
3. Menemukan rantai RNA dari 120 daftar kemungkinan tersebut yang
disusun oleh G-fragment, yang memiliki kesamaan urutan fragmen dengan
U, C-fragment (seperti yang diketahui), jika rantai RNA tersebut dipecah
oleh U, C-Enzyme. Dan ditemukan rantai RNA pada urutan ke- 26
(UCGAGCUAGCGAAG) yang mana rantai tersebut jika dipecah oleh U,
C-Enzyme menjadi U, C-fragment yaitu U, C, GAGC, U, AGC, GAAG,
seperti yang diketahui. Maka rantai RNA aslinya adalah
UCGAGCUAGCGAAG .
Rekonstruksi rantai RNA dengan cara acak/manual dapat dikatakan
efektif tergantung dari jumlah fragmen (dalam hal ini adalah n) yang
digunakan. Apabila semakin banyak jumlah fragmen yang akan digunakan
pada langkah pertama yaitu pada pembuatan n!, maka akan semakin banyak
pula penyusunan kemungkinan rantai RNA tersebut sehingga makna efektif
sebelumnya dapat berubah menjadi kurang efektif.
Selain itu, dapat pula terjadi kemungkinan rantai RNA yang unik
artinya tidak dapat ditemukan dari kesekian n! kemungkinan rantai yang
tersusun dari salah satu fragmen yang apabila rantai tersebut dipecah oleh
enzim lainnya tidak ditemukan fragmen dari enzim lainnya yang dimaksud.
Dengan kata lain, untuk fragmen yang unik maka rekonstruksi rantai RNA
tidak dapat dipecahkan dengan menggunakan cara acak/manual.
Aplikasi Sirkuit Euler..., Ari Prasetiyowati, FKIP UMP, 2010