| 초록 |
여러 생물에 관련된 genomic data가 급속히 증가하고, data를 빠르고 정확하게 분석할 수 있게 되었다. 이러한 data들을 다루는 방법 중의 하나인 multiple sequence alignment는 세 개 이상의 단백질이나 DNA 서열들을 배열하여서 유사하거나 같은 부분을 찾아낸다. 기존의 SP-method, CLUSTALW, PILEUP 을 비롯한 multiple sequence alignment 방법들은 pairwise comparison 을 하므로 서열의 개수가 증가할수록 검색 시간이 크게 증가하는 단점이 있다. 따라서 pairwise comparison을 하지 않고 여러 개의 서열들을 동시에 비교하기 위해 Suffix Tree Clustering알고리즘을 구현하여 multiple sequence alignment에 적용하고 gene clustering의 5단계를 제시하였다. i)Constructing suffix tree ii)Searching and overlapping common subsequences iii)Grouping subsequence pairs iv)Masking cross-matching pairs v)Clustering pair groups. Suffix Tree Construction 은 서열길이에 비례하는 선형시간 알고리즘으로써 genomic data같은 대용량의 데이터를 다루기에 효율적이다. 우리는 Perl language를 이용해 유전자들을 유사성에 따라 clustering하는 suffix tree clustering program 을 만들었고, 프로그램을 평가하기 위해, Mus musculus 종에서 가져온 23개의 유전자를 입력했을 경우와 다른 종들에서 가져온 22개의 유전자를 입력했을 때의 두 가지 경우로 나누어서 multiple sequence alignment를 수행하고 clustering 하였다. |
