Z-align: An Exact and Parallel Strategy for Local Biological Sequence Alignment in User-Restricted Memory Space
作者： Rodolfo Batista , Alba Magalhaes Alves De Melo
DOI: 10.1109/CLUSTR.2006.311858
关键词: Space (mathematics) 、 Algorithm 、 Computer science 、 Parallel algorithm 、 Theoretical computer science 、 Divergence (statistics) 、 Computational complexity theory 、 Function (mathematics) 、 DNA sequencing 、 Affine transformation 、 Cluster (physics)
摘要: The algorithm proposed by Smith-Waterman is an exact method that obtains optimal local alignments in quadratic space and time. For long sequences, complexity makes the use of this impractical. In scenario, parallel computing a very attractive alternative. paper, we propose evaluate z-align, strategy based on divergence concept to locally align biological sequences using affine gap function. Z-align runs limited memory space, where amount used can be defined user. results collected cluster with 16 processors presented good speedups for real DNA sequences. By comparing obtained z-align BLAST, it clear able produce longer more significant alignments.
ieeecomputersociety.org参考文章(22)
Kevin Charter, Duane Szafron, Jonathan Schae, Sequence Alignment using FastLSA ,(2000)
Peiyi Tang, Pen-Chung Yew, Processor self-scheduling for multiple-nested parallel loops international conference on parallel processing. pp. 528- 535 ,(1986)
Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Suffix Trees and Their Uses ,(1997) , 10.1017/CBO9780511574931
Azzedine Boukerche, Alba Cristina Magalhaes Alves de Melo, Mauricio Ayala-Rincon, Thomas M. Santana, Parallel smith-waterman algorithm for local DNA comparison in a cluster of workstations Lecture Notes in Computer Science. pp. 464- 475 ,(2005) , 10.1007/11427186_40
Gregory F. Pfister, In search of clusters: the coming battle in lowly parallel computing Prentice-Hall, Inc.. ,(1995)
A. Apostolio, C. Guerra, A Fast Linear Space Algorithm for Computing Longest Common Subsequences ,(1985)
Joao Carlos Setubal, Joao Meidanis, . ̤ Setubal-Meidanis, Introduction to Computational Molecular Biology ,(1997)
Renata Cristina F. Melo, Maria Emília Telles Walter, Alba Cristina Magalhaes Alves Melo, Rodolfo Batista, Marcelo Nardelli, Thelmo Martins, Tiago Fonseca, Comparing Two Long Biological Sequences Using a DSM System european conference on parallel processing. pp. 517- 524 ,(2003) , 10.1007/978-3-540-45209-6_74
Stephen F. Altschul, Bruce W. Erickson, OPTIMAL SEQUENCE ALIGNMENT USING AFFINE GAP COSTS Bulletin of Mathematical Biology. ,vol. 48, pp. 603- 616 ,(1986) , 10.1007/BF02462326
Dan Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology ,(1997)