Meeting Agenda

Wednesday, May 8, 1996

Location:

DC 1304

Time:

1:30 PM

Chair:

Bala Balakumaran

---

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:

Any volunteers?

Coffee hour next week:

Any volunteers?

3. Next meeting

Date:

May 15, 1996

Location:

DC 1304

Time:

1:30 PM

Chair:

Richard Bartels

Technical presentation:

Thomas Pflaum

4. Forthcoming

Chairs:

1. John Beatty
2. Leith Chan
3. Leo Chan

Tech Presenters:

1. Randall Reid
2. Navid Sadikali
3. Bala Balakumaran

5. Technical Presentation

Presenter:

Mike McCool

Title:

Distributed Objects and CORBA

Abstract:

Distributed objects under CORBA are object-oriented ``components'' that are language and location independent. They are an abstraction that hides the network layer, so applications can be written using a collection of distributed objects as if they were all local objects, modulo network latency. CORBA is an evolving standard which allows the definition of the interface to an object to be mapped into multiple languages, and which defines a set of runtime services that provide location independence, persistence, locking, naming, introspection, and so forth. Sun's "NEO Workshop" CORBA development environment is being made available in the lab; if anyone wants to use it to develop distributed applications (for example, distributed VR or rendering) you're more than welcome. The development environment also includes the user interface tools from OpenStep.

6. General Discussion Items

Fabrice will announce new lab duty list.

7. Action List

8. Director's Meeting

9. Seminars

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    - Wednesday, May 8, 1996

Bhaskar DasGupta, University of Waterloo, will speak on
``On Distances between Phylogenetic Trees''.

TIME:                2:30-3:30 p.m.

ROOM:                DC 1331

ABSTRACT

Different  phylogenetic  trees  for  the  same group of
species  are  often  produced either by procedures that
use diverse optimality criteria or from different genes
in  the  study of molecular evolution.  Comparing these
trees  to  find  their  similarities (e.g. agreement or
consensus) and dissimilarities (i.e. distance), is thus
an  important issue in computational molecular biology.
The nearest neighbor interchange (nni) distance and the
subtree-transfer   distance   are  two  major  distance
metrics that have been proposed and extensively studied
for  different  reasons.   Despite their many appealing
aspects  such  as  simplicity  and  sensitivity to tree
topologies, computing these distances has remained very
challenging.   In this talk we study the complexity and
efficient  approximation  algorithms  for computing the
nni  distance  and  a natural extension of the subtree-
transfer  distance,  called  the  linear-cost  subtree-
transfer  distance.  The  linear-cost  subtree-transfer
model  is  more  logical  than the (unit-cost) subtree-
transfer model and in fact coincides with the nni model
under  certain  conditions.  The following results have
been  obtained  as  part  of  our project of building a
comprehensive  software package for computing distances
between phylogenies.

1.  Computing  the  nni  distance  is NP-complete. This
    solves  a 25 year old open question appearing again
    and   again.   We  also  answer  an  open  question
    regarding  the nni distance between unlabeled trees
    for  which  an erroneous proof appeared before.  We
    give  an  algorithm  to  compute  the  optimal  nni
                          O(d)
    sequence in time O(n.2    ), where the nni distance
    is at most d.  The algorithm allows us to implement
    practical  programs  when  d  is  small.  All above
    results also hold for linear-cost subtree-transfer.

2.  Biological  applications  require  us to extend the
    nni  and  linear-cost  subtree-transfer  models  to
    weighted  phylogenies,  where edge weights indicate
    the length of evolution along each edge. We present
    a logarithmic ratio approximation algorithm for nni
    and  a  ratio 2 approximation algorithm for linear-
    cost subtree-transfer, on weighted trees.

Joint    work   with   Xin   He   (SUNY-Buffalo),   Tao
Jiang(McMaster),   Ming  Li(Waterloo)  and  John  Tromp
(CWI).

---

10. Lab Cleanup (until 1:30 or 5 minutes)