advertisement

MAVisto A tool for the exploration of network motifs By Guo Chuan & Shi Jiayi 2016/3/16 www.brainybetty.com 1 CONTENTS The Tool —— MAVisto Frequency concept Flexible search Application 2016/3/16 www.brainybetty.com 2 The Tool —— MAVisto Background The Tool Execution 2016/3/16 www.brainybetty.com 3 Frequency concept Definitions Pattern Frequency 2016/3/16 www.brainybetty.com 4 Background A general way to understand complex biological networks is to break them down into the simplest units of commonly used network architecture. Such patterns of local interconnection are called network motifs. They have been found in many different networks. Examples: A well-known motif is the feed-forward loop which performs key information processing roles in cells the prediction of interaction partners of proteins in protein-interaction networks 2016/3/16 www.brainybetty.com 5 There are two tools for network motif analysis Mfinder : without any means of visual analysis Pajek : 2016/3/16 it finds only motifs with three vertices www.brainybetty.com 6 The Tool MAVisto (Motif Analysis and VISualization TOol) It provides a flexible motif search algorithm and different views for the analysis and visualization of network motifs. 2016/3/16 www.brainybetty.com 7 The advanced layout algorithm An advanced force-directed layout algorithm is included to generate nice drawings of the network automatically which preserve the layout of motifs where possible 2016/3/16 www.brainybetty.com 9 Definitions A directed graph G = (V,E) consists of a finite set V of vertices and a finite set E ⊂ V*V of edges. An edge (u, v) ∈ E goes from vertex u, the source, to another vertex v, the target. The vertices u and v are said to be incident with the edge e and adjacent to each other. A subgraph of the graph G = (V,E) is a graph Gs = (Vs,Es) where Vs ⊂ V and Es ⊂ (Vs *Vs) ∩E. For a graph G and a subgraph Gs an edge e = (u, v) ∈ E is called incident to Gs if exactly one of the vertices u, v is element of the set Vs. 2016/3/16 www.brainybetty.com 10 The in-degree of a vertex is defined as the number of edges coming into the vertex, the out-degree as the number of edges going out of it. The degree of a vertex is the number of all edges connected to it. The pattern size is the number of edges that the pattern comprises 2016/3/16 www.brainybetty.com 11 GT be a graph representing the biological network to be analysed (the target network) and GP be a graph representing the pattern of interest. A match GM is a subgraph of GT which is isomorphic to GP 2016/3/16 www.brainybetty.com 12 Pattern Frequency Different concepts for determination of pattern frequency The frequency of a pattern in a target graph is the maximum number of different matches of this pattern. There are different concepts for determining the frequency of a pattern depending on which elements of the graph can be shared by two matches 2016/3/16 www.brainybetty.com 13 graph (a), a pattern (b) and all different matches of the pattern (c,M1 −M5) 2016/3/16 www.brainybetty.com 14 Frequency concept F1 counts every match of this pattern. This concept gives a complete overview of all possible occurrences of a pattern even if elements of the target graph have to be used several times. It does not exclude possible matches (as the other concepts often do) and therefore shows the full ‘potential’ of the target graph with regard to the pattern Frequency concepts F2 and F3 restrict the reuse of graph elements shared by different matches of a pattern Concept F2 only allows edge disjoint matches Concept F3 is even more restrictive concerning sharing graph elements of the target graph for different matches. All matches have to be vertex and edge disjoint 2016/3/16 www.brainybetty.com 15 2016/3/16 www.brainybetty.com 16 Downward closure property of the frequency An important feature for the presented search algorithm is the downward closure property of the frequency of the patterns The search algorithm traverses the patterns like a tree where the downward closure property ensures that the frequency of descending patterns is monotonically decreasing with increasing size of the pattern. 2016/3/16 www.brainybetty.com 17 The downward closure property holds for frequency concepts F2 and F3, but not for F1 2016/3/16 www.brainybetty.com 18 (a) a graph of size 9 and two patterns of (b) size 3 and (c) size 4. The pattern in (c) is a one-edge extension of the pattern in (b). The frequency of the pattern in (b) within the target graph in (a) is one for the three concepts. For the pattern in (c) the number of matches within the target graph in (a) is one for concept F2 and F3 and six for concept F1 In the latter case the numberof matches increases for a pattern which is an extension of another pattern and hence is not downward closed 2016/3/16 www.brainybetty.com 19 Flexible search Overview Algorithm Details of FPF 2016/3/16 www.brainybetty.com 20 Overview the frequent pattern finder (FPF) algorithm searches for patterns of a given size (the target size) which occur with maximum frequency under a given frequency concept The pattern tree FPF uses a method that builds a tree of only the patterns which are supported by the target graph and traverses this tree such that only promising branches are examined 2016/3/16 www.brainybetty.com 21 The pattern tree .Note that there are more patterns of size 3 indicated by dashed lines. 2016/3/16 www.brainybetty.com 22 Algorithm The search starts The search is done The search terminates Two algorithm The search terminates 2016/3/16 www.brainybetty.com 23 The search starts The search starts with the smallest pattern p of size 1 which consists of one edge and two vertices. All matches Mp1 of this pattern are generated using every edge once. On the basis of the matches m ∈Mp of a pattern p of size i all one edge extension patterns p' of size i + 1, which have p as generating parent, are created. 2016/3/16 www.brainybetty.com The search terminates 24 The search is done This is done in the following way: for every match m all incident edges within the graph are identified and are used successively to create a new match m' of size i + 1. 2016/3/16 www.brainybetty.com The search terminates 25 The search terminates The search process terminates if no patterns of intermediate size are left for extension 2016/3/16 www.brainybetty.com The search terminates 26 Search for a set of patterns with highest frequency Specification of a threshold for minimum frequency Parallel processing of the pattern extension Parallel processing of different branches of the search tree 2016/3/16 www.brainybetty.com 27 Search for a set of patterns with highest frequency Specification of a threshold for minimum frequency Parallel processing of the pattern extension Parallel processing of different branches of the search tree 2016/3/16 www.brainybetty.com 28 Details of PFP Generating parent Canonical label Iterative Partitioning Maximum independent set The search terminates 2016/3/16 www.brainybetty.com 29 Generating parent A pattern of size i can be derived from up to i different patterns of size i-1 by adding one edge. In order to avoid the redundant generation of a pattern only one defined pattern of size i-1 is allowed to generate this pattern, the generating parent. 2016/3/16 www.brainybetty.com The search terminates 30 Canonical label The canonical label is a unique identifier of a graph or pattern invariant to the ordering of the vertices and edges. By comparing the canonical labels graphs can be checked for isomorphism. The method used for the generation of a canonical label is the transformation of the adjacency matrix into a string by concatenating it row-by-row. Solution 2016/3/16 www.brainybetty.com The search terminates 31 Iterative Partitioning The iterative partitioning algorithm is a method to calculate a fine-grain partitioning of the vertices on the basis of vertex invariants. How is work 2016/3/16 www.brainybetty.com The search terminates 32 Maximum independent set The maximum independent set S of a graph G = (V,E) is defined as the largest subset of vertices of V such that no pair of vertices of S defines an edge of E. 2016/3/16 www.brainybetty.com The search terminates 33 Application 2016/3/16 www.brainybetty.com 34