.: 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