Effective Biological Sequence Alignment Method using Divide Approach

다국어 초록 (Multilingual Abstract)

This paper presents a new sequence alignment method using the divide approach, which solves the problem by decomposing sequence alignment into several sub-alignments with respect to exact matching subsequences. Exact matching subsequences in the proposed method are bounded on the generalized suffix tree of two sequences, such as protein domain length more than 7 and less than 7. Experiment results show that protein sequence pairs chosen in PFAM database can be aligned using this method. In addition, this method reduces the time about 15% and space of the conventional dynamic programming approach. And the sequences were classified with 94% of accuracy

참고문헌 (Reference)

1 송영옥, "바이오 데이터 패턴 분석을 위한 시스템 및 알고리즘 설계" 한국콘텐츠학회 10 (10): 104-110, 2010

2 유기동, "문서 자동요약 기술을 적용한 클라우드 스토리지 기반 지능적 아카이빙 시스템" 한국산업정보학회 17 (17): 59-68, 2012

3 Sean R. Eddy, "Where did the BLOSUM62 alignment score matrix come from?" 22 : 1035-1046, 2004

4 Marco Punta1, "The Pfam protein families database" 1-12, 2011

5 Alex Bateman, "The PFAM Protein Family Database" 30 (30): 276-280, 2002

6 J. Karkkainen, "Sparse Suffix Tree" COCOON 219-233, 1996

7 M.I. Abouelhoda, "Replacing suffix trees with enhances suffix arrays" 2 (2): 53-86, 2004

8 E. Ukkonen, "On-line Construction of Suffix-Trees" 14 : 249-260, 1995

9 D.K.Kim, "Linearized suffix tree : an efficient index data structure with the capabilities of suffix trees and suffix arrays" 52 (52): 350-377, 2008

10 Josue Samayoa, "Identification of prokaryotic small proteins using a comparative genomic approach" 27 (27): 1765-1771, 2011

11 오윤신, "Identification of 1,531 cSNPs from Full-length Enriched cDNA Libraries of the Korean Native Pig Using in Silico Analysis" 한국유전체학회 7 (7): 65-84, 2009

12 Batzoglou, S, "Human and mouse gene structure: comparative analysis and application to exon prediction" 10 : 950-958, 2000

13 L.Russo, "Fully- Comoressed suffix trees" LATIN 362-373, 2008

14 Mark Nelson, "Fast String Searching With Suffix Trees" 1996

15 X. Guan, "Domain identification by clustering sequences alignment" 14 (14): 783-788, 1998

16 Chan Park, "Design and Implementation of Bio-Medical Data Measurement System through the Stereo Microscope" 7 (7): 357-360, 2009

17 "Data Structure and Algorithm: Tree and Suffix trees" Mcgill University 1997

18 Audry P. G., "Conservation and Evolution of Cis-Regulatory Systems in Ascomycete Fungi" 2 (2): 398-405, 2004

19 P. Agarwal, "Comparative accuracy of methods for protein sequences similarity search" 14 (14): 40-47, 1998

20 David W., "Bioinformatics, sequences and Genome Analysis" MOUNT Press 2001

21 I. Mihalek, "Background frequencies for residue variability estimates: BLOSUM revisited" 8 : 488-498, 2007

22 D. Gusfield, "Algorithms on strings, trees, and sequences : Computer science and Computational biology" CAMBRIDGE University Press 1997

23 이성열, "A Modified Heuristic Algorithm for theMixed Model Assembly Line Balancing" 한국산업정보학회 15 (15): 59-65, 2010