| In a bio logical network,the network motif serves as a const ituent unit o f a co mplex network,and is considered to be the basic unit reflect ing the cooperat io n model o f the bio logical network.Therefore,it is an important analyt ical too l to reveal the characteristics o f bio logical networks for stu dying network motifs.Bio logical networks can be divided into ho mogeneous networks and heterogeneous networks according to the t ypes o f nodes.Amo ng them,the co-regulat ion network is a heterogeneous network.Co mpared with the isomorphic network o f protein interact ion,it has the characterist ics o f large scale and many t ypes o f nodes and regulator y mechanisms.The co-regulat ion network contains three t ypes o f nodes,namely mi RNA,transcript ional regulators and genes.There are five kinds o f regulat ion functions in the co-regulat ion network.These regulat ion funct ions provide opportunit ies for understanding and studying the laws o f life act ivit ies.However,since the network mot if discovery algorithm includes subgraph enumerat ion and subgraph iso morphism judg ment,where the subgraph iso morphism judgment is NP co mplete problem,the network motif discovery is a very co mputat ionally intensive task.Co mbining parallelizat ion techno logy,two network mot if discovery algorithms are proposed.The main research work is as follows:(1)Considering the resources o f a single computer,it takes a long t ime for CPU co mput ing resources to process large-scale co-regulat ion networks.In response to the above problems,this paper proposes a GPU-based co-regulatorynetwork mot if discovery algorithm CMGPU.The algorithm allocates threads according to the mi RNA number;the subgraph iso morphism judgment and subgraph enumeration run on the GPU,the co-regulatory network performs subpicture enumerat ion through the ESU algorithm,and ensures that the subgraph is only enumerated once,and the subgraph passes an integer Subst itute subgraph labels for iso morphic judgment and reduce GPU memory consumpt ion;finally,use the CPU for rando m network generat ion and saliency calculat ion.By analyz ing the mot if discovered by the CMGPU algorithm;it is proved that CMGPU algorithm can find the bio logical model.In co mparison wit h the CPU-based network mot ifs discovery algorithm,the experimental results show that CMGPU algorithm improves the subgraph enumerat io n and the subgraph iso morphism judgment process,and the mot ifs discovery t ime is reduced by 90% when the mot ifs size is 4(2)The number of threads based on a single co mputer is limited,result ing in slower processing of large-scale data.For this problem.this paper proposes a network mot ifs discovery algorithm(CMSP)based on Spark.CMSP implements subgrap h enumerat ion through parallelizat ion,subgraph iso morphism,and rando m network generat ion to accelerate the mot if recognit io n step.The algo rithm firstly distributes the t ypes o f network nodes and the set o f node neighbors to different machines in the cluster through a broadcast function through data preprocessing,and enumerates the subgraphs o f the network by exhaust ive method and sampling m ethod.In this stage,it is proposed to replace the subgraphs with edges to generate a sequence o f tuples,determine whether the subgraphs are iso morphic through the sequence o f tuples,and then use the Map Reduce idea to reduce the number of subgraph isomo rphism judgments and accelerate the iso morphism judgment process.Using the advantages o f Spark clusters,mult i-threaded rando m network generat ion.The experiment proves that the CMSP algorithm has scalabilit y,and also verifies that the sampling algorithm can improve the speed of network mot if discovery on the premise o f ensuring the final result. |
