복수서열정렬 프로그램

From Opengenome.net
복수서열정렬 프로그램
 
Sequence alignments는 gene의 특성이 파악된 gene과 새로이 발견된 gene을 비교하는 매우 강력한 방법이다. 잘 제작된 queries와 alignments로부터 functional information뿐만 아니라 evolutionary information도 추출할 수 있다. BLAST(Basic Local Alignment Search Tool)은 뉴클레오타이드 데이타베이스(nucleotide database)와 단백질 데이터베이스(protein database)의 신속한 검색 방법을 제공한다. BLAST에서 사용하는 알고리즘은 global alignment뿐만 아니라 local alignment도 탐지한다. 이들 모든 타입의 similarity는 미지의 단백질의 기능에 대한 중요한 단서를 제공할 수도 있다.
 
BLAST또는 PSI-BLAST search 알고리즘을 사용하여 관심있는 family를 대략 정의한 후, 관심있는 family에 속하는 sequence를 FASTA포맷의 non-redundant 파일로 모은다.
크기가 다른 member를 제거하거나 query와 관련이 없는 extra sequence를 trimming하여 family members의 리스트를 refine한다.
 
Multiple alignment 프로그램을 선택한다. Clustal W알고리즘은 널리 사용되면서도 맥킨토시, 윈도우즈 및 유닉스 플랫폼에서 무료로 사용할 수 있는 프로그램으로 제공된다. 세 개 이상의 sequence를 gap을 추가하여 common structural positionas또는 common ancestry를 가진 residue의 alignment로 최적화하는 과정을 multiple alignment라 한다.
 
Multiple alignment 프로그램은 각각의 sequence를 collection내에 있는 다른 sequence와 pairwise방식으로 비교하여 각각의 sequence pair의 relative relatedness에 기반하여 distance matrix와 phylogenetic tree를 구성한다. Phylogenetic tree를 사용하여 alignment를 만든다. 추가적인 less related sequence를 추가하면서 alignment가 조정되고, 예상되는 secondary structure의 유의하면서 필요한 경우 gap가 추가한다.
 
Dynamic Programming
 
전산에서 많이 이용되는 programming 기술로 한번 계산되어 얻어진 값을 이용해 전체로 확장 시켜 나가면서 마지막 해답을 얻는 경우에 이용되는 algorithm 이다. 일반적으로 Dynamic Programming 은 해결 가능한 방법이 많고, 그 중 최적의 것을 찾는 것이 필요한 경우에 사용된다. 이 algorithm 은 sequence comparison, sequence alignment 에 쓰인다.
 
1)    Needleman-Wunsch Algorithm (Global Alignment)
Dynamic Programming 을 이용한 algorithm으로 global alignment 에 쓰인다. 이 algorithm 에서 사용되는 scoring matrix 의 각 position 은 positive or negative score or 0 을 가진다. 이 algorithm 을 이용한 alignment 는 주변의 higher-scoring alignment 에 의해 broken pattern 이 생겨 놓치는 region 이 생길 수 있다. 그래서 Smith-Warterman algorithm 이 local alignment 에서 conserved region 을 찾아내기 위해 개발되었다.
 
2)    Smith-Warterman Algorithm (Local Alignmenmt)
Local alignment 는 conserved region 을 포함하기 때문에 global alignment 보다 훨씬 의미가 있다. 이 algorithm 이 Needleman-Wunsch algorithm 과 다른 점은 dynamic programming scoring matrix 에서 negative score(mismatched) 가 나오면 그 값을 0 으로 바꾼다. 이 algorithm 에서는 lower scoring alignment 도 가능하다. 그리고 같은 aligned amino acid pairs를 이용한 multiple local alignment 도 가능하다.
 
 
 
참고문헌
1.    Andreas D. Baxevanis, B. F. Francis Ouellette. Bioinformatics. Wiley-Interscience.2001.
2.    KOBIC Biocourse http://biocourse.org
4.    NCBI Education :http://www.ncbi.nlm.nih.gov/Education/
6.    Molecular Station: http://www.molecularstation.com/
 


Retrieved from "http://Opengenome.net/index.php?title=복수서열정렬_프로그램&oldid=27270"