Parallelization of KMP algorithm for the masking-off of repeats in DNA fragment assembly

摘要

DNA fragment assembly is one the most important aspects of bioinformatics. A new parallelizing optimizing method based on KMP algorithm is proposed in this paper with the aim of dealing with the problem of masking-off of repeats during the DNA fragment assembly. This parallelizing optimizing method divides the target sequence into several parts by the idea of divide and rule, then the main processor assigns each part of sequences to corresponding processors with parallel pattern matching by KMP algorithm. This parallelizing optimizing method can reduce time complexity and the computer simulation has proved the effectiveness of the method.