Identifying Variable-Length Palindromic Pairs in DNA Sequences

게놈 프로젝트 연구는 DNA사슬 내에서 생물학적 의미(예, molecule의 진화역사 또는 그 기능)를 추출하기위한 사슬분석 쪽으로 강조가 되어가고 있다. 특히, DNA사슬 내에서 상보적 또는 반복되는 패턴은 생물학적 의미를 가지고 있다. 문제는 상보적 단어가 만들어내는 흥미 있는 패턴과 단어 구성을 찾아 내는 것이다. 본 논문은 다양한 길이의 팰린드롬 쌍을 검색하는 알고리즘에 관한 연구이다. 다양한 길이의 팰린드롬 쌍 내에는 빈 공백을 또한 허용한다. 알고리즘은 팰린드롬 알고리즘이라고 명명하며 O(N)의 계산 시간을 가진다. 하나의 팰린드롬 쌍은 머리핀 형태로 구성되어 있다. 검출된 여러 팰린드롬 쌍을 활용하여 n-쌍 팰린드롬 형태를 구성하였다. 더욱이 발견된 가장 긴 팰린드롬 쌍을 DNA 사슬 원형 구조에 점으로 표현하여 가시성을 제고하였다. 본 알고리즘은 여러 게놈 상에서 실시되었으며 E.coli K12의 결과를 나타내었다. 실험결과 DNA 안에는 랜덤한 경우에는 확률상 매우 발생하기 힘든 긴 팰린드롬 패턴들이 존재 한다는 것을 발견할 수 있었다. The emphasis in genome projects has Been moving towards the sequence analysis in order to extract biological "meaning"(e.g., evolutionary history of particular molecules or their functions) from the sequence. Especially. palindromic or direct repeats that appear in a sequence have a biophysical meaning and the problem is to recognize interesting patterns and configurations of words(strings of characters) over complementary alphabets. In this paper, we propose an algorithm to identify variable length palindromic pairs(longer than a threshold), where we can allow gaps(distance between words). The algorithm is called palindrome algorithm(PA) and has O(N) time complexity. A palindromic pair consists of a hairpin structure. By composing collected palindromic pairs we build n-pair palindromic patterns. In addition, we dot some of the longest pairs in a circle to represent the structure of a DNA sequence. We run the algorithm over several selected genomes and the results of E.coli K12 are presented. There existed very long palindromic pair patterns in the genomes, which hardly occur in a random sequence.