Abstract | ||
---|---|---|
BACKGROUND: Network methods are increasingly used to represent the interactions of genes and/or proteins. Genes or proteins that are directly linked may have a similar biological function or may be part of the same biological pathway. Since the information on the connection (adjacency) between 2 nodes may be noisy or incomplete, it can be desirable to consider alternative measures of pairwise interconnectedness. Here we study a class of measures that are proportional to the number of neighbors that a pair of nodes share in common. For example, the topological overlap measure by Ravasz et al. 1 can be interpreted as a measure of agreement between the m = 1 step neighborhoods of 2 nodes. Several studies have shown that two proteins having a higher topological overlap are more likely to belong to the same functional class than proteins having a lower topological overlap. Here we address the question whether a measure of topological overlap based on higher-order neighborhoods could give rise to a more robust and sensitive measure of interconnectedness. RESULTS: We generalize the topological overlap measure from m = 1 step neighborhoods to m ≥ 2 step neighborhoods. This allows us to define the m-th order generalized topological overlap measure (GTOM) by (i) counting the number of m-step neighbors that a pair of nodes share and (ii) normalizing it to take a value between 0 and 1. Using theoretical arguments, a yeast co-expression network application, and a fly protein network application, we illustrate the usefulness of the proposed measure for module detection and gene neighborhood analysis. CONCLUSION: Topological overlap can serve as an important filter to counter the effects of spurious or missing connections between network nodes. The m-th order topological overlap measure allows one to trade-off sensitivity versus specificity when it comes to defining pairwise interconnectedness and network modules. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1186/1471-2105-8-22 | BMC Bioinformatics |
Keywords | Field | DocType |
higher order,bioinformatics,algorithms,gene network,microarrays | Adjacency list,Adjacency matrix,Pairwise comparison,Topology,Biology,Fungal protein,Gene co-expression network,Bioinformatics,Genetics,Gene regulatory network,Interconnectedness | Journal |
Volume | Issue | ISSN |
8 | 1 | 1471-2105 |
Citations | PageRank | References |
59 | 4.58 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andy M. Yip | 1 | 232 | 20.65 |
Steve Horvath | 2 | 747 | 50.14 |