Bioinformatics | DNA Sequence Alignment (Global Alignment)

DNA 서열 Alignment 에는 Global과 Local Alignment가 있다.

 

Global Alignment 는 유전자 서열 전체 길이와 함께 두 서열을 비교하고 정렬하여 최대로 정렬된 뉴클레오타이드 또는 아미노산을 보여주기 위한 정렬이다. 

 

 

두 개의 서열이 있을 때 시작점부터 정렬하여 서열 끝까지 비교하며 가장 유사한 특성의 sequence를 뽑아내는 것이다. 

 

Two Sequence 가 아래와 같다고 했을 때,

 - AGTGATG  &  GTTAG

 

Scoring을 하고 backtracking하며 alignment를 뽑아내면 된다. 

Scoring할 때 +, - 점수는 임의로 정해서 진행하면 된다. 필자는 두 서열의 유전자가 같을 때는 +2점 다를 때는 -1점을 부여했다. 

 

Scoring Matrix

	#	A	G	T	G	A	T	G
#	0	-2	-4	-6	-8	-10	-12	-14
G	-2	-1	-1	-3	-5	-7-	-9	-11
T	-4	-3	-2	0	-2	-4	-6	-8
T	-6	-5	-4	-1	-1	-3	-3	-5
A	-8	-5	-6	-3	-2	0	-2	-4
G	-10	-7	-4	-5	-2	-2	-1	-1

Backtracking Matrix

	#	A	G	T	G	A	T	G
#	0	-2	-4	-6	-8	-10	-12	-14
G	-2	-1	-1	-3	-5	-7-	-9	-11
T	-4	-3	-2	0	-2	-4	-6	-8
T	-6	-5	-4	-1	-1	-3	-3	-5
A	-8	-5	-6	-3	-2	0	-2	-4
G	-10	-7	-4	-5	-2	-2	-1	-1

마지막 셀로부터 왼쪽, 왼쪽 대각선, 위의 score를 비교하며 가장 큰 값으로 backtracking한다. 

 

AGTGATG를 소스, GTTAG를 타겟이라고 칭했을 때

왼쪽 대각선으로 갈 때는 양 서열에 같은 문자를 출력하고,

왼쪽으로 갈 때는 소스에는 문자를 출력, 타겟에는 '-'를 출력하고 위 쪽으로 갈 때는 소스에는 '-', 타겟에는 문자를 입력하면된다. 

 

결과는 다음과 같이 출력된다. 

 

Result

source = AGTGATG target = -GTTA-G

 

Source Code

import java.util.*;

public class DNAAlignment {
	public static void main(String[] args) {
    	String dna1 = "AGTGATG";
        String dna2 = "GTTAG";
  
  		Alignment score = align(dna1, dna2);
  		System.out.println(score);
        System.out.println("Score = " + score.score());
    }
 
 	private static Alignment align(String dna1, String dna2) {
  		if (dna1.length() == 0 && dna2.length() == 0) {
	   		return new Alignment();
	  	} else if (dna1.length() == 0) {
   			Alignment result = align(dna1, dna2.substring(1));
   			result.addMatch('-', dna2.charAt(0));
   			return result;
  		} else if (dna2.length() == 0) {
   			Alignment result = align(dna1.substring(1), dna2);
   			result.addMatch(dna1.charAt(0), '-');
   			return result;
  		} else {
   			Alignment first = align(dna1.substring(1), dna2);
   			first.addMatch(dna1.charAt(0), '-');
   
			Alignment second = align(dna1, dna2.substring(1));
   			second.addMatch('-', dna2.charAt(0));
   
			Alignment both = align(dna1.substring(1), dna2.substring(1));
   			both.addMatch(dna1.charAt(0), dna2.charAt(0));
   
   			if (first.score() >= second.score() && first.score() >= both.score()) {
    			return first;
   			} else if (second.score() >= first.score() && second.score() >= both.score()) {
    			return second;
   			} else {
    			return both;
   			}
  		}
 	} 
 
 
//----------------HELPER CLASS------------------
// Represents an alignment of two strands of DNA.
 private static class Alignment {
 	String dna1;
  	String dna2;
  
// Create a new alignment with no characters included.
	public Alignment() {
   		dna1 = "";
   		dna2 = "";
  	}
  
// Adds c1 to the front of the first DNA sequence,
// adds c2 to the front of the 2nd DNA sequence.
	public void addMatch(char c1, char c2) {
   		dna1 = c1 + dna1;
   		dna2 = c2 + dna2;
  	}
  
  	public int score() {
   		int score = 0;
   		for (int i = 0; i < dna1.length(); i++) {
    		if (dna1.charAt(i) == dna2.charAt(i)) {
     			score += 2;
	    	} else {
			     score -= 1;
    		}
   		}
   		return score;  
  	}
  
// Returns each DNA sequence on its own line.
	public String toString() {
   		return dna1 + "\n" + dna2;
  	}
}