PMC:4331680 / 11472-16615 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/4331680","sourcedb":"PMC","sourceid":"4331680","source_url":"https://www.ncbi.nlm.nih.gov/pmc/4331680","text":"Identifying major types of network motifs\nThere are a number of publicly available network motif detection tools, namely MFINDER [13], MAVISTO [41], FANMOD [42], NetMatch [43], and SNAVI [44]. The main disadvantage of using MFINDER and MAVISTO for network motif detection is that they are comparably slow and scale poorly as the subgraph size increases [22,42]. We have performed a trial study using FANMOD with KEGG data as input, the tool reports subgraphs that occur significantly more often than in random networks. The tool does not provide information on; 1) how many subgraphs are found, and 2) subgraph's nodes identities. In other words, no detail of real motif is supplied. For instance, the output file of FANMOD reports certain motif information, such as frequency of occurrence, Z-value and p-value, however, it does not report nodes identities, then one does not know which genetic elements belong to the motif. In other words, given the pairwise information as input, FANMOD can predict over-represented motifs with certain level of accuracy, but it does not report nodes identities.\nAlso, FANMOD has certain limitation, for instance, it cannot identify motifs with size one and two, i.e. auto-regulation loop and feedback loop. This can be done with the adjacency matrix description. More details are given in the 'Results' section Table 2.\nTable 2 A comparison of motif finding by the adjacency matrix approach and FANMOD\napproach motif AML Glioma Melanoma NSCLC PC RCC\nAdjacency Matrix FFL 0 § 0 § 0 § 1 1 1\nbi-fan 1 § 1 § 1 1 0 § 0 §\nFANMOD FFL 0 § 0 § 0 § 0 (FN) 0 (FN) 0 (FN)\nbi-fan 1 § 1 § 0 (FN) 0 (FN) 0 § 0 §\nNon bi-fan 2(2)* 1(1)* 0(0)* 2(2)* 3(3)* 3(1)*\n§given a fixed motif size, the italic and underlined fonts denote the results uisng adjacency matrix approach are consistent with those of FANMON, i.e. true positive or true negative events\n* the first number denotes the number of identified motifs, the number inside the parenthesis denotes the total number of motif pattern found in the cancer type Because of this limitation, we have developed a motif searching algorithm, which is able to process KEGG networks, such as; the 'pathways in cancer (overview)' for human, and found a cFFL that involves genes PKC, Ras and Raf. It is interesting to note that this loop participates in coordination of crosstalk between the Ras/Raf and PKC pathways [23,45].\nWe also tested our motif-searching algorithm for the plant pathogen interaction network, and found two FFLs, where the first FFL involves CNGCs with Ca++, CDPK and Rboh, and the second FFL involves MEKK1, MKK1 and MPK4. It is known that the first FFL is associated with Ca++ signaling [46] whereas the second FFL that involves MEKK1, MKK1 and MPK4 is associated with plant immune responses [47-49]. This demonstrates the usefulness of identifying or matching network motifs with functional biological modules.\nIn the graph theory approach, each bio-molecule is represented as a node and regulatory relation as an edge. One constructs an adjacency matrix to represent the network. In the adjacency matrix a value of one and infinity (for convenient a very large number is used in programming) is assigned to represent direct regulation and non-regulating nodes respectively. For node that is interacting with itself a value of one is assigned. Row and column indices denote the upstream and downstream node respectively. Below we briefly described how to perform the motif search.\n\nARL\nThis motif type involves a self-regulated gene. Non-zero diagonal elements in the adjacency matrix represent this type of motif. The time complexity is O(n).\n\nFBL\nThis motif type involves two genes regulate each other. For any location(i, j) in the adjacency matrix, if the term of (i,j) is '1' and that of (j,i) is also '1', then genes i and j form a FBL. Since there are C(n,2) combinations to be tested, the time complexity is O(n2).\n\nFFL\nThis motif type involves three genes regulating each other. Depending on the activation or suppression order, this motif type can be further divided into the so-called cFFL, and iFFL.\nFor any triple set (i,j,k), if the terms of (i,j), (j,i),(i,k),(k,i), (j,k),(k,j) are all of '1', then genes i , j and k form a FFL. Since there are C(n,3)*6 combinations to be tested, the time complexity is O(n3).\n\nBi-fan\nBi-fan motif denotes a topology where two genes regulate the same other two genes.\nSelect any two rows in the adjacency matrix which have the value of '1' appear at the same column more than one time. Check whether these two rows are connected, if not, then determine which two columns have the value of '1' in both rows. The time complexity is O(n3). To identify all bi-fan motifs, there are C(n,2)*C(n-2,2) combinations to check, so the time complexity is O (n4).\n\nSIM\nSIM motif denotes a topology where a master gene regulates multiple downstream genes.\nSelect any row in the adjacency matrix and count how many '1' appear in the row. Since there are at most n '1's in a row and n rows to search; therefore, the time complexity is O(n2).","divisions":[{"label":"title","span":{"begin":0,"end":41}},{"label":"p","span":{"begin":42,"end":1098}},{"label":"p","span":{"begin":1099,"end":1356}},{"label":"table-wrap","span":{"begin":1357,"end":2113}},{"label":"label","span":{"begin":1357,"end":1364}},{"label":"caption","span":{"begin":1366,"end":1439}},{"label":"p","span":{"begin":1366,"end":1439}},{"label":"table","span":{"begin":1440,"end":1762}},{"label":"tr","span":{"begin":1440,"end":1494}},{"label":"th","span":{"begin":1440,"end":1448}},{"label":"th","span":{"begin":1450,"end":1455}},{"label":"th","span":{"begin":1457,"end":1460}},{"label":"th","span":{"begin":1462,"end":1468}},{"label":"th","span":{"begin":1470,"end":1478}},{"label":"th","span":{"begin":1480,"end":1485}},{"label":"th","span":{"begin":1487,"end":1489}},{"label":"th","span":{"begin":1491,"end":1494}},{"label":"tr","span":{"begin":1495,"end":1549}},{"label":"td","span":{"begin":1495,"end":1511}},{"label":"td","span":{"begin":1513,"end":1516}},{"label":"td","span":{"begin":1518,"end":1524}},{"label":"td","span":{"begin":1526,"end":1532}},{"label":"td","span":{"begin":1534,"end":1540}},{"label":"td","span":{"begin":1542,"end":1543}},{"label":"td","span":{"begin":1545,"end":1546}},{"label":"td","span":{"begin":1548,"end":1549}},{"label":"tr","span":{"begin":1550,"end":1594}},{"label":"td","span":{"begin":1550,"end":1556}},{"label":"td","span":{"begin":1558,"end":1564}},{"label":"td","span":{"begin":1566,"end":1572}},{"label":"td","span":{"begin":1574,"end":1575}},{"label":"td","span":{"begin":1577,"end":1578}},{"label":"td","span":{"begin":1580,"end":1586}},{"label":"td","span":{"begin":1588,"end":1594}},{"label":"tr","span":{"begin":1595,"end":1654}},{"label":"td","span":{"begin":1595,"end":1601}},{"label":"td","span":{"begin":1603,"end":1606}},{"label":"td","span":{"begin":1608,"end":1614}},{"label":"td","span":{"begin":1616,"end":1622}},{"label":"td","span":{"begin":1624,"end":1630}},{"label":"td","span":{"begin":1632,"end":1638}},{"label":"td","span":{"begin":1640,"end":1646}},{"label":"td","span":{"begin":1648,"end":1654}},{"label":"tr","span":{"begin":1655,"end":1709}},{"label":"td","span":{"begin":1655,"end":1661}},{"label":"td","span":{"begin":1663,"end":1669}},{"label":"td","span":{"begin":1671,"end":1677}},{"label":"td","span":{"begin":1679,"end":1685}},{"label":"td","span":{"begin":1687,"end":1693}},{"label":"td","span":{"begin":1695,"end":1701}},{"label":"td","span":{"begin":1703,"end":1709}},{"label":"tr","span":{"begin":1710,"end":1762}},{"label":"td","span":{"begin":1710,"end":1720}},{"label":"td","span":{"begin":1722,"end":1727}},{"label":"td","span":{"begin":1729,"end":1734}},{"label":"td","span":{"begin":1736,"end":1741}},{"label":"td","span":{"begin":1743,"end":1748}},{"label":"td","span":{"begin":1750,"end":1755}},{"label":"td","span":{"begin":1757,"end":1762}},{"label":"table-wrap-foot","span":{"begin":1763,"end":2113}},{"label":"p","span":{"begin":1763,"end":1952}},{"label":"p","span":{"begin":1953,"end":2113}},{"label":"p","span":{"begin":2114,"end":2468}},{"label":"p","span":{"begin":2469,"end":2978}},{"label":"p","span":{"begin":2979,"end":3548}},{"label":"sec","span":{"begin":3550,"end":3711}},{"label":"title","span":{"begin":3550,"end":3553}},{"label":"p","span":{"begin":3554,"end":3711}},{"label":"sec","span":{"begin":3713,"end":3990}},{"label":"title","span":{"begin":3713,"end":3716}},{"label":"p","span":{"begin":3717,"end":3990}},{"label":"sec","span":{"begin":3992,"end":4394}},{"label":"title","span":{"begin":3992,"end":3995}},{"label":"p","span":{"begin":3996,"end":4179}},{"label":"p","span":{"begin":4180,"end":4394}},{"label":"sec","span":{"begin":4396,"end":4868}},{"label":"title","span":{"begin":4396,"end":4402}},{"label":"p","span":{"begin":4403,"end":4485}},{"label":"p","span":{"begin":4486,"end":4868}},{"label":"title","span":{"begin":4870,"end":4873}},{"label":"p","span":{"begin":4874,"end":4959}}],"tracks":[{"project":"2_test","denotations":[{"id":"25707690-12399590-14863464","span":{"begin":130,"end":132},"obj":"12399590"},{"id":"25707690-16020473-14863465","span":{"begin":144,"end":146},"obj":"16020473"},{"id":"25707690-16455747-14863466","span":{"begin":157,"end":159},"obj":"16455747"},{"id":"25707690-17277332-14863467","span":{"begin":172,"end":174},"obj":"17277332"},{"id":"25707690-18940806-14863468","span":{"begin":188,"end":190},"obj":"18940806"},{"id":"25707690-15193307-14863469","span":{"begin":354,"end":356},"obj":"15193307"},{"id":"25707690-16455747-14863470","span":{"begin":357,"end":359},"obj":"16455747"},{"id":"25707690-16626682-14863471","span":{"begin":2461,"end":2463},"obj":"16626682"},{"id":"25707690-17370427-14863472","span":{"begin":2464,"end":2466},"obj":"17370427"},{"id":"25707690-15377221-14863473","span":{"begin":2755,"end":2757},"obj":"15377221"},{"id":"25707690-17644023-14863474","span":{"begin":2860,"end":2862},"obj":"17644023"},{"id":"25707690-18570633-14863474","span":{"begin":2860,"end":2862},"obj":"18570633"},{"id":"25707690-20304701-14863474","span":{"begin":2860,"end":2862},"obj":"20304701"}],"attributes":[{"subj":"25707690-12399590-14863464","pred":"source","obj":"2_test"},{"subj":"25707690-16020473-14863465","pred":"source","obj":"2_test"},{"subj":"25707690-16455747-14863466","pred":"source","obj":"2_test"},{"subj":"25707690-17277332-14863467","pred":"source","obj":"2_test"},{"subj":"25707690-18940806-14863468","pred":"source","obj":"2_test"},{"subj":"25707690-15193307-14863469","pred":"source","obj":"2_test"},{"subj":"25707690-16455747-14863470","pred":"source","obj":"2_test"},{"subj":"25707690-16626682-14863471","pred":"source","obj":"2_test"},{"subj":"25707690-17370427-14863472","pred":"source","obj":"2_test"},{"subj":"25707690-15377221-14863473","pred":"source","obj":"2_test"},{"subj":"25707690-17644023-14863474","pred":"source","obj":"2_test"},{"subj":"25707690-18570633-14863474","pred":"source","obj":"2_test"},{"subj":"25707690-20304701-14863474","pred":"source","obj":"2_test"}]}],"config":{"attribute types":[{"pred":"source","value type":"selection","values":[{"id":"2_test","color":"#93ecca","default":true}]}]}}