Comparison Architecture for Large Number of Genomic Sequences
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Generally, a suffix tree is an efficient data structure since it reveals the detailed internal structures of given sequences within linear time. However, it is difficult to implement a suffix tree for a large number of sequences because of memory size constraints. Therefore, in order to compare multimega base genomic sequence sets using suffix trees, there is a need to re-construct the suffix tree algorithms. We introduce a new method for constructing a suffix tree on secondary storage of a large number of sequences. Our algorithm divides three files, in a designated sequence, into parts, storing references to the locations of edges in hash tables. To execute experiments, we used 1,300,000 sequences around 300Mbyte in EST to generate a suffix tree on disk.
Abstract
Generally, a suffix tree is an efficient data structure since it reveals the detailed internal structures of given sequences within linear time. However, it is difficult to implement a suffix tree for a large number of sequences because of memory size constraints. Therefore, in order to compare multimega base genomic sequence sets using suffix trees, there is a need to re-construct the suffix tree algorithms. We introduce a new method for constructing a suffix tree on secondary storage of a large number of sequences. Our algorithm divides three files, in a designated sequence, into parts, storing references to the locations of edges in hash tables. To execute experiments, we used 1,300,000 sequences around 300Mbyte in EST to generate a suffix tree on disk.
참고문헌 (19)
- Hardison, R. C., "Long human-mouse sequence alignments reveal novel regulatory elements : a reason to sequence the mouse genome", Genome Research, 7, pp.959~966 (1997)
- Dunham, I., "The DNA sequence of human chromosome", Nature, 40, pp.489~495 (1999)
- 오윤신, "Identification of 1,531 cSNPs from Full-length Enriched cDNA Libraries of the Korean Native Pig Using in Silico Analysis", Genomics & Informatics, 7(2), pp.65~84 (2009), 한국유전체학회
- Audry, P. G., "Conservation and Evolution of Cis-Regulatory Systems in Ascomycete Fungi", PLOS Biology, 2(12), pp.398~405 (2004)
- 이우기, "유전 알고리즘을 이용한 웹 클러스터링 시뮬레이션", 정보기술아키텍처 연구, 7(1), pp.111~121 (2010), 한국ITA학회
- 강복영, "비획득 정보 처리를 위한 대체 기반 실시간 비즈니스 프로세스 모니터링 방법론 개발", 정보기술아키텍처 연구, 7(2), pp.161~170 (2010), 한국ITA학회
- Altschul, S. F., "Gapped BLAST and PSIBLAST: a new generation of protein database search programs", Nucleic Acids Research, 25, pp.3389~3402 (1997)
- "Crossmatch" (2009)[URL]
- Schwartz, S., "A web server for aligning two genomic DNA sequences", Genome Research, 10, pp.577~586 (2000)
- Delcher, A. L., "Alignment of whole genomes", Nucleic Acids Research, 27, pp.2369~2376 (1999)
- Batzoglou, S., "Human and mouse gene structure: comparative analysis and application to exon prediction", Genome Research, 10, pp.950~958 (2000)
- Juha Karkkainen, "Sparse Suffix Tree", COCOON, 1, pp.219~233 (1996)
- Kurtz, S., "Reducing the Space Requirement of Suffix Trees", Software Practice and Experience, 29, pp.1149~1171 (1999)
- Abouelhoda, M. I., "Replacing suffix trees with enhances suffix arrays", Journal of Discrete Algorithms, 2(1), pp.53~86 (2004)
- Kim, D. K., "Linearized suffix tree: an efficient index data structure with the capabilities of suffix trees and suffix arrays", Algorithmica, 52(3), pp.350~377 (2008)
- Russo, L., "Fully-Comoressed suffix trees", LATIN, pp.362~373 (2008)
- Dan Gusfield, "Algorithms on strings, trees, and sequences: Computer science and Computational biology" (1997), CAMBRIDGE University Press
- Ukkonen, E., "On-line Construction of Suffix-Trees", Algorithmica, pp.249~260 (1995)
- Mark Nelson, "Fast String Searching With Suffix Trees", Dr. Dobb's Journal (1996)