Parallel Optimization And Implementation Of Rapid Drug-discovery Algorithms Based On Massively Expression Profiling

With the advent of 21 st century,a variety of new viruses,such as Anthrax mail and SARS,in the world are endless.The potential biological threats far outweigh the scope of traditional bioterrorism agents and potent pathogens.How to respond quickly and efficiently to the challenges of these sudden viruses is a worldwide problem.At the same time,with the rapid development of biotechnology,the experimental methods and research methods in biomedical field have undergone tremendous changes,showing an explosion of output data.The expression profiling data can be used to compare gene expression levels among normal and abnormal cells,help identify disease-related genes and drug targets,analyze the pathogenesis of complex diseases,and provide guidance for personalized diagnosis and treatment.Based on these conditions,we choose the analysis of mass expression data as the starting point and analyze the existing problems and challenges of rapid Drug-Discovery.Then we carry out a thorough research on three important aspects,including expression profiling,the massively expression profile comparison and cluster and frequent subgraph mining,combine the Tianhe-2 supercomputer,and design two new parallel algorithms.Our approaches improve the time and space efficiency efficiently,with the precision maintaining.Our work includes:1.GSEA(Gene Set Enrichment Analysis)algorithm is a worldwide recognized expression profiling algorithm.But limited by its complex computing process,the existing implementations are difficult to achieve the required speed of analysis.To solve the problem,we redesign the algorithm by pre-sorting,constructing Triple,establishing inverted index,removing the prefix sum and so on.By optimization,the overall time complexity of ES calculation is reduced from O(m*n)to O(m+n)and thereby we implement a massively expression profile parallel query algorithm.In the experiment,our algorithm presents up to two orders of magnitude faster than original GSEA implementations even on a single core CPU and shows linear scalability.2.The CMap project,which is based on GSEA,presents an excellent practice of rapid Drug-Discovery.Unfortunately,it does not provide an effective calculation tool.Based on the optimization of the GSEA algorithm,we design and implement a parallel comparison algorithm for mass expression profiles,adopt a variety of strategies to divide the initial data to achieve load balance and combine MPI with OpenMP to accomplish the second level parallel acceleration.Experiments show that our algorithm built a complete connectively map on LINCS PHASE I dataset with around 100 hours and gain a speedup of around 96 times in the 96-core high-performance server.Further,we can find that the analysis time of whole profiles can be further reduced within one hour on a 1000-node cluster on Tianhe-2 with a near-linear speedup.Based on the similarity matrix of expression profiling,we also design a parallel clustering algorithm based on KMedoids algorithm.It completes the parallelization in each iteration to avoid the dependence.The experimental results show that the proposed algorithm has good convergence and high efficiency of massively expression profile clustering.Also,the Kappa indicator shows the accuracy of clustering results.3.Another technique for rapid Drug-Discovery driven by mass profile data is largescale network analysis.Through the GSEA algorithm,the correlation matrix and mapping network among various types of pathogen and human cell response expression profiles are constructed,which can be used to discover damaged pathways of human body through large-scale network mining and thereby aid the rapid drug discovery process.We mainly focus on a sub-problem of network mining method,named Frequent Subgraph Mining(FSM),which lacks effective parallel acceleration implementations.On the other hand,most of the existing parallelization algorithms do not use heuristic strategies,which are inefficient and basically no multi-node version.To solve these problems,we design a scalable parallel frequent subgraph mining algorithm,realizing parallelism of multiple levels and multiple granularities and utilizes MIC as accelerator on Tianhe-2.We develop fine-grained parallelism of multi-thread by translate DFS recursive mining process into a BFS loop mining process.Four kinds of static task dividing strategy and a supervisorbased dynamic task dividing strategy are implemented to achieve best load balancing.Further,we adopt distributed strategy to ease memory pressure,adjust key graph structure and back up complex data structures redundantly to avoid the bottlenecks caused by excessive transmission.By making full use of the multi-core computing capacity of MIC,we can achieve a desired effect of execution speed in the scenario of CPU and MIC collaboration.Finally,our algorithm presents more than 50 times speedup on Tianhe-2 single node and maintains a good scalability on multi-node.Especially,we can obtain at least more than 500 X speedup on 16 Tianhe-2 nodes.