Exercises marked with (*) require further reading/search beyond the suggested texts.
2. Find the connected compontents in the strictly overlapping graph for the clones x probes matrix below.
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0
Answer:
The graph is easier to construct if the clones are represented by sets of probes:
| S1 = | {3, 8} |
| S2 = | {4, 7} |
| S3 = | {2, 4, 5, 7, 9, 10} |
| S4 = | {3, 6} |
| S5 = | {4, 5, 9} |
| S6 = | {1, 2, 4, 5, 7, 9} |
| S7 = | {3, 4, 5, 6, 7, 8, 9} |
| S8 = | {7} |
Each set will be a vertex of the graph. For an edge to be drawn between any two vertices Si and Sj, the statements below must be true:
The graph that fulfills those conditions is:
Resulting in 4 connected components.
© 2015 Joao Meidanis