文章基本信息

标题：PARALLEL MODEL AND SCHEDULING TECHNIQUE FOR SPACES COMPLEXITY AND SYNCHRONIZATION PROBLEMS IN SEQUENCES ALIGNMENT
本地全文：下载
作者：MANHAL ELFADIL ELTAYEEB ; MUHAMMAD SHAFIE ABD LATIF ; ISMAIL FAUZI ISNIN 等
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2014
卷号：63
期号：2
出版社：Journal of Theoretical and Applied
摘要：Biologists are confusing with the huge amount of data resulting from conformations of DNA and protein sequences. In an earlier stage, a dot-plot method is used to identify new sequences. It is based on comparing sequences in a level of graphical illustration to detect similar locations of sequences. However, for long sequences this method is impractical. Furthermore, Improvement method using sequential machine adopted by Needleman-Wunsch (NW) and Smith-Waterman (SW) algorithms, where sequences set in a matrix with scoring system and optimal alignment via dynamic programming method is achieved. Unfortunately, these algorithms suffer from time and space complexity. An alternative approach is necessary to compare long sequences in a reasonable time with respect to memory restrictions. In this paper, we developed a new parallel model with implementing scheduler-worker paradigm and a scheduling technique. Our model is based on Bulk Synchronous Parallelism (BSP) model, where each worker has its own distributed memory and accomplish selected number of blocks. Using X86-based PC with eight logical processors we are able to compare sequences range from 411 KBP to 4 MBP in O((m+n/w)/w) space and linear communication complexity.
关键词：DNA and Protein; Sequences Comparisons; Parallel Model; Memory and Communications Complexities