| Homology search is the basic research topic of bioinformatics. Biologist can get similar sequences of the query sequence from database by homology search, and rapidly obtain a lot of valuable reference information, which will be helpful for analyzing furthermore. Traditional homology search tools based on sequence information have been well developed, but they are not applicable for RNA homology search. Along with rising of researching in the non-coding RNA domain, RNA homology search problem attracts more and more attention. Currently, the method based on Covariance Model is widely used because of its high sensitivity, extensive applicability and less manual works. However, its correlative algorithms are of high complexity, which restricts its application. As the biology data increases rapidly, it is very exigent to develop efficient parallel algorithms utilizing existing computing resources. This thesis mainly investigates how to improve the speed of RNA homology search in high performance computing environment. Its main works and contributions are summarized as follows:1. After analyzing data dependencies of scanning CYK algorithm, we introduce matrix blocking techniques according to the characteristics of three-dimension matrix and present a new parallel algorithms based on pipeline technology. Moreover, a load balance strategy is given based on load estimation.2. An efficient implementation of pipeline parallel algorithms based on lock function of OpenMP is presented and is applied on the scanning CYK parallel algorithm above. The testing results indicate that the proposed algorithms and implementation are of high efficiency.3. After analyzing serial program of cmsearch,based on optimized two-level work pool strategy, a new parallel version is given. Furthermore, The parameter problem involved in the two-level work pool is discussed. Test results shows that the parallel method has good scalability, and can be used in solving large-scale homologous RNA search problem. |
PDF Full Text Request