CGL Meeting Agenda - 2000.01.26

January 26th, 2000

Location:
Computer Graphics Lab
Time:
11:30 a.m.
Chair:
Maggie Dulat 
Member List

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:
Anybody?
Coffee hour next week:
None.

3. Next meeting

Date:
Wednesday, February 2nd, 2000
Location:
DC1304
Time:
11:30 a.m.
Chair:
Roger Fernandes (February 2nd) 
Technical presentation:
Bill Cowan (February 2nd) 

4. Forthcoming

Chair:
  1. Teresa Ge (February 9th) 
  2. Erik Demaine (February 16th) :-)
  3. Patrick Gilhuly (February 23rd) 
Tech Presenters:
  1. Maggie Dulat  (February 9th)
  2. Erik Demaine (February 16th) :-)
  3. Roger Fernandes  (February 23th)

5. Technical Presentation

Presenter:
Blair Conrad (January 26th) 
Title:
How to Survive Without a Lab Manager
Abstract:

I'm leaving, and there's no new lab manager lined up. This presentation contains hopefully helpful advice on

  1. getting by until a new lab manager is chosen, and even
    2. afterward
  2. speeding the lab manager's indoctrination

6. General Discussion Items

7. Action List

8. Director's Meeting (last week's)

  1. Recruiting: Vladimir Baranoski

9. Seminars

Wednesday, 26 January 2000, 3:00PM -- MC5136
Seminar -- Combinatorics and Optimization
Speaker: Kerri Webb, Dept. of Combinatorics & Optimization, University of Waterloo
Title: "Combinatorial Optimization Seminar - The Rank of the Matching Forest Matrix"
Abstract:A mixed graph G=(V,E,A) is a graph with both undirected edges E, and directed edges A. In 1982, Giles introduced the concept of a matching forest in G: the subset F of undirected and directed edges is a matching forest of G if

- F\A is a matching in (V,E)

- F\E is a branching in (V,A)

- F contains no cycles in the underlying undirected graph for G

Let T be the Tutte matrix for (V,E) and let B be the branching matrix for (V,A). Tutte showed that the rank of T is twice the size of a maximum matching of (V,E), and Chaiken and Kleitman (1978) related the determinant of B to the number of branchings of (V,E). Using these results, we show that the rank of T+B is the maximum number of vertices covered by a matching forest in G.

We also present an algorithm that uses the methods of Geelen (97,98) to find an integer evaluation C of T+B, such that the rank of C is equal to the rank of T+B.

Wednesday, 26 January 2000, 3:30PM -- DC1304
Algorithms and Complexity Group - M. Math. thesis presentation -- Computer Science
Speaker: Haoyong Zhang, Dept. of Computer Science, University of Waterloo
Title: "Design, implementation and analysis of a novel quartet-based phylogenetic reconstruction method "
Abstract:It is now routine for biologists to conduct evolutionary analyses of large DNA and protein sequence datasets. A computational bottleneck in these analyses is the recovery of the topology of the evolutionary tree for a set of sequences. This thesis presents a practical solution to this challenging problem. In particular, a new technique, called _Hypercleaning_, is presented that can be combined with various tree-building algorithms to efficiently reconstruct from sequence data the best supported edges of the evolutionary tree. More precisely, the Hypercleaning technique computes from sequence data a small subset of edges that is likely to contain most edges of the correct tree. A tree-building algorithm then attempts to identify edges in the subset that are compatible with each other and hereby produces an evolutionary tree.

We also propose a simple greedy algorithm, and introduce other possible paradigms that build a tree by screening the edges provided by Hypercleaning in the decreasing order of support from sequence data. Extensive simulation studies are also presented to demonstrate the efficiency and effectiveness of Hypercleaning.

10. Lab Cleanup