PMC:1481596 / 36712-37865 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":"Graphs that have tree of complexes representation\nThe COD method is not guaranteed to produce the Tree of Complexes representation for every possible protein interaction network. How can a family of graphs that admit Tree of Complexes representation be characterized? First, we argue that chordal graphs belong to this family. It can be shown that addition of edges that connect weak siblings does not introduce chordless cycles to the graph. Therefore, after all weak siblings are connected the graph is still chordal and thus admits Tree of Complexes representation. Next, we argue that cographs admit Tree of Complexes representation. Our methods eliminates all the squares in the graph, unless every possible set of eliminating edges forms a P4, which is entirely contained in one of the maximal cliques of the modified graph. It can be shown that the latter case is possible only when the original graph contains a P4, and thus is not a cograph. We conjecture that graphs that admit Tree of Complexes representation are exactly those graphs that admit a clique tree representation, with the nodes being maximal cographs rather than maximal cliques.","divisions":[{"label":"title","span":{"begin":0,"end":49}}],"tracks":[]}