PMC:1481596 / 33905-34994 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1481596","sourcedb":"PMC","sourceid":"1481596","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1481596","text":"Edge addition\nWe use a reduction to the Minimum Vertex Cover problem to find all minimal sets of up to k edges that eliminate all the squares in the graph.\nEach eliminating set of edges, S = {e1,..., er}, is assigned a cost:\nwhere sim(ei) takes values between 1.0 and 0.0, and measures our confidence in adding ei to the graph. Since the addition of ei = (ui, vi) implies an interaction or functional equivalence between proteins ui and vi, we chose sim(ei) to be the amount of overlap between the neighborhoods of ui and vi, i.e., sim(ei) = , where (vi) denotes a set of neighbors of node vi in the graph. Intuitively, sim(ei) measures how close ui and vi are to being a pair of weak siblings. If ui and vi have the same neighborhoods then sim(ei) = 1.0; as the overlap between the neighborhoods decreases, sim(ei) goes to 0.0. Then, we pick an edge set with the minimum cost from all the edge sets that do not form a P4, which is entirely contained in one of the maximal cliques of the modified graph. The last requirement is necessary to ensure that each functional group is a cograph.","divisions":[{"label":"title","span":{"begin":0,"end":13}},{"label":"p","span":{"begin":14,"end":155}},{"label":"p","span":{"begin":156,"end":224}}],"tracks":[]}