DNA사슬 내에서 다양한 길이의 팰린드롬쌍 검색 연구
Identifying Variable-Length Palindromic Pairs in DNA Sequences
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
게놈 프로젝트 연구는 DNA사슬 내에서 생물학적 의미(예, molecule 의 진화역사 또는 그 기능)를 추출하기위한 사슬분석 쪽으로 강조가 되어가고 있다. 특히, DNA사슬 내에서 상보적 또는 반복되는 패턴은 생물학적 의미를 가지고 있다. 문제는 상보적 단어가 만들어내는 흥미 있는 패턴과 단어 구성을 찾아 내는 것이다. 본 논문은 다양한 길이의 팰린드롬 쌍을 검색하는 알고리즘에 관한 연구이다. 다양한 길이의 팰린드롬 쌍 내에는 빈 공백을 또한 허용한다. 알고리즘은 팰린드롬 알고리즘이라고 명명하며 O(N)의 계산 시간을 가진다. 하나의 팰린드롬 쌍은 머리핀 형태로 구성되어 있다. 검출된 여러 팰린드롬 쌍을 활용하여 n-쌍 팰린드롬 형태를 구성하였다. 더욱이 발견된 가장 긴 팰린드롬 쌍을 DNA 사슬 원형 구조에 점으로 표현하여 가시성을 제고하였다. 본 알고리즘은 여러 게놈 상에서 실시되었으며 E.coli K12 의 결과를 나타내었다. 실험결과 DNA 안에는 랜덤한 경우에는 확률상 매우 발생하기 힘든 긴 팰린드롬 패턴들이 존재 한다는 것을 발견할 수 있었다.
Abstract
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.
참고문헌 (18)
- A. Apostolico, "Parallel dtection of all palindromes in a string", 141(1), pp.163~173 (1995)
- A.H.L. Porto, "Finding approximate palindromes in strings", pp.2581~1591 (2002)
- D. Breslauer, "Finding all periods and initial palindromes of a string in parallel", 14(4), pp.355~366 (1995)
- D. Gusfield, "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology" (1997), Cambridge University Press, New York, NY
- Larry, "The Cartoon Guide To Genetics", pp.147~148 (1983)
- J.A. Eisen, "Evidence for symmetric chromosomal inversions around the replication origin in bacteria", 1(6) (2000)
- J. Jurka, "Origin and evaluation of alu repetitive elements", pp.25~41 (1995), R.G. Landes, New York, NY
- Wang, "Discovering active motifs in sets of related protein sequences and using them for classification", pp.2769~2775 (1994)
- K. Shishido, "ncreased production of a knotted form of plasmid pbr322 DNA in Escherichia coli DNA topisomeraes mutants", pp.215~218 (2003)
- L.J. Jensen, "Three view of microbial genomes", pp.773~777 (1999)
- National Center for Biotechnology Information, "complete genome sequence of Salmonella enterica serovar typhimurium LT2" (2003)
- National Center for Biotechnology Information, "The complete genome sequence of Escherichia coli O157" (2003)
- National Center for Biotechnology Information, "The complete genome sequence of Escherichia coli K12" (2001)
- S.F. Altschul, "also claimed that BLAST will have O(N2) time complexity to find all palindromes" (2003)
- T.H. Cormen, "Introduction to Algorithms", pp.857~861 (1998), New York: McGraw-Hill
- T.L. Bailey, "Discovering motifs in DNA and protein sequences" (1995)
- T. Tsunoda, "Time and memory efficient algorithm for extracting palindromic and repetitive subsequences in nucleic acid sequences Pacific Symposium on Biocomputing 4", pp.202~213 (1999)
- X. Guan, "A fast look-up algorithm for detecting repetitive DNA sequences, Pacific Symposium on Biocomputing", pp.718~719 (1996)