Efficient Serial and Parallel Algorithms for Selection of Unique Oligos in EST Databases

[摘要] Obtaining unique oligos from an EST database is a problem ofgreat importance in bioinformatics, particularly in the discovery ofnew genes and the mapping of the human genome. Many algorithmshave been developed to find unique oligos, many of which are muchless time consuming than the traditional brute force approach. Analgorithm was presented by Zheng et al. (2004)which finds the solution of the unique oligos search problem efficiently. We implement this algorithm as well as several new algorithms basedon some theorems included in this paper. We demonstrate how, withthese new algorithms, we can obtain unique oligos much faster thanwith previous ones. We parallelize these new algorithms to furtherimprove the time of finding unique oligos. All algorithms are run onESTs obtained from a Barley EST database.

[学科分类] 生物技术