Neighbour Joining [AlgorBio]

Neighbour join (NJ) merupakan sebuah metode dalam bioinformati yang digunakan untuk mengklusterkan secara Bottom-Up data-data dari sebuah DNA.
Algoritma NJ dapat dituliskan seperti berikut:
1. Inisialisasi
2. Pilih node i,j yang minimum Dij*
    gabungkan node i,j menjadi node k
    Dij*=Dij-(R1+R2)
    Ri= rata-rata jarak antara node i dan rest dari node j
    Rj= rata-rata jarak antara node j dan rest dari node i
3. Gambar node k pada phylogenic tree
    d(km)=1/2 (d(im)+d(jm)+d(ij))
    dan hubungkan k ke i dan j dengan
       d(ik)= 1/2 (d(ij)+Ri-Rj)
       d(jk)= 1/2 (d(ij)-Ri+Rj)

contoh soal:
seq1: AGCAG
seq2: AGTCG
seq3: ACATG
seq4: AGTAC

dari seguence diatas dapat kita dapatkan tabel berikut yang merupakan proses inisialisasi yang sama dengan progresive method.

Dij*=Dij-(R1+R2)
D12*=0.4-0.47-0.47=-0.54
D13*=0.6-0.47-0.67=-0.54
D14*=0.4-0.47-0.53=-0.60 [min] (selected)
D23*=0.6-0.47-0.67=-0.54
D24*=0.4-0.47-0.53=-0.60 [min]
D34*=0.8-0.67-0.67=-0.40

karena yang kita pillih D14* maka setelah itu kita mencari jarak antara node 1 dan 4 dengan node baru 5, dengan cara:

akan kita gabungkan node 1 dan node 4 menjadi node 5:
Dkm=1/2 (Dim+Djm-Dij)
D52=1/2 (D12+D42-D14)=1/2 (0.4+0.4-0.4)=0.4
D53=1/2 (D13+D43-D14)=1/2 (0.6+0.8-0.4)=0.5

D52*=0,2-0.35-0.40=-0.55 (selected)
D53*=0.5-0.35-0.55=-0.40
D23*=0.6-0.04-0.55=-0.35

D63=1/2 (D53+D23-D25)=1/2 (0.5+0.6-0.2)=0.35

Make Profile From Sequence [AlgorBio]

pada postingan kali ini aka dibahas cara membuat profile dari satu set sequence. apa sih gunanya profiling ini? ya, jika kita ingin meng-alignment sequence-sequence kitaa harus menghitungnya dengan metode-metode yang pernah kita bahas sebelumnya, mulai dari star method maupun progresive alignment. maka dari itu ketika kita telah menghitung satu set multiple kita lebih baik membuat profile dari alignment yang sudah ada, sehingga jika ada sequence baru yang akan di alignment, kita tidak perlu lagi mengihitung dari awal lagi menggunakan metode sebelumnya. berikut cara membuat profile dari satu set sequence:

dalam suatu kasus dimana sequence baru akan masuk. maka:

maka hasil akhirnya sebagai berikut:

Heuristic Approaches for MSA [ArgorBio]

          Heuristic Approaches merupakan teknik yang lebih baik untuk membandingkan antar sequence.  Terdapat dua macam pendekatan secara Heuristic, yaitu:
1. Star Method
2. Progresive (tree base) Method

Pertama akan dibahas pendekatan heuristik dengan menggunakan metode star. metode ini masih tetap menggunakan Dynamic Programing tetapi tidak langsung membandingkan kesemua sequence, tetapi membandingkan setiap dua-dua sequence.

contoh soal:
Seq 1 : A G G A
Seq 2 : A T G C G T
Seq 3 : A T G C G A

jawab :
step 1: bandingkan dengan DP seq1 dengan seq2

setelah menghitung semua kombinasi dari setiap sequence kita mendapatkan semua nilai yang dapat kita rangkum dalam sebuah tabel berikut.

dari nilai diatas kita mendapatkan nilai yang paling tinggi yaitu pada baris terakhir. 

Selanjutnya, yang kedua kita membahas tentang pendekatan Heuristik menggunakan Progrseive (Tree based) Method.

contoh soal;
dengan sequen yang sama seperti yang dibandingkan dengan star method
Seq 1 : A G G A
Seq 2 : A T G C G T
Seq 3 : A T G C G A

dapat disimpulkan bahwa penggunaan kedua metode tersebut menghasilkan keluaran yang sama, hal ini dimungkinkan karena jumlah panjang sequence dan komposisi sequencenya. dalam kasus lain hasil star method dan progresive report dapat menghasilkan keluaran yang berbeda. secara umum perbedaan step antara star method dan progresive method dijabarkan dari tabael dibawah ini:

Multiple Sequence Alignment [AlgorBio]

          Multiple Sequence Alignmet yaitu dimana kita membandingkan lebih dari dua sequence dan kita diminta untuk mendapatkan score maksimal dari satu set sequence setelah dibandingkan dengan sequence lain serta membuat profile. secara umum kita bisa mendapatkan nilai scoring dari MSA dengan rumus:

sedangkan ada dua metode untuk mendapatkan nilai S(mi):

1. Sum of Pair (SP) 

 

contoh soal:

2. Minimum Entropy

   

contoh soal:

Sequence Alignment by Dynamic Programing [ArgorBio]

       Sequence Alignment merupakan cara mengetahui kemiripan dua buah sequence dimana sequence-sequence yang ingin dibandingkan akan disejajarkan. Cara yang paling mudah untuk mengetahui kemiripan dua buah sequence yaitu dengan cara melihat dan langsung menetapkan apakah sequence tersebut similar atau tidak. cara lain yang dapat digunakan untuk mengetahui kemiripannya yaitu dengan menggunakan Dinamic Programing. pada tulisan kali ini saya akan membahas tentang cara menggunakan Dynamic Programing untuk membandingkan dua sequence.

dalam Sequence Alignment terdapat dua hal yang dibandingkan, yaitu
A. Global Alignment
B. Local Alignment

A. Pertama akan kita bahas Global Alignment terlebih dahulu.
[Algoritma] terdapat tiga tahap dalam kasus ini:
1. Inisialisasi (cell kuning)
    Isi tepi matriks dengan nilai nol.

2. mengisi nilai matriks (cell biru)
    isi matriks

3. Trace back
 Pada Global Alignment dilakukan dari score yang optimal yaitu dari nilai matrik M[m,n] menuju inisalisasi cell (0) yang mana saja.

 

contoh soal:

 jawab:

trace back:

B. kedua akan kita bahas local Alignment.
perbedaan yang paling mendasar antara global alignment dan local alignment terdapat pada step ketiga yaitu pada proses traceback, dimana proses traceback awal dilakukan dimilai dari nilai maksimal dari matrik tersebut bukan dari nilai optimalnya. tetapi tidak memiliki nilai negatif alias memiliki nilai minimal 0.