Class Discussions 3/3/10
4.5.1 Divisive Algorithms for Mapping Onto A Tree – Use calculated betweenness to work backwards from a complete graph to remove edges and construct a tree. Use Girven-Newman Algorithm to choose which edges to cut:
Girven-Newman Algorithm
1. The betweenness of all existing edges is calculated.
2. The edge with the highest betweenness is removed.
3. The betweenness of all edges affected by the removal is calculated.
4. Repeat steps 2 and 3 until no edges remain.
4.7 Network Growth Mechanisms – models to represent how different networks grow and replicate. Duplication-Divergence Mechanism, duplication of vertex=duplication of gene. Duplication-Mutation-Complementation (DMC) based on model that most genes have been preserved by functional complementation. Duplication-Random Mutations (DMR). Some of this material really confused me, particularly how the edges were removed in the DMC algorithm. At least I understood how the edges changed with the addition of the duplicated vertices.
