Snir, 4/6, 1:30, on a problem derived from evolutionary biology

From: Martin Tompa (tompa@cs.washington.edu)
Date: Mon Mar 22 2004 - 11:32:20 PST

  • Next message: beame@cs.washington.edu: "Time & Room Change: CSE 590Z Theory Seminar"

    Please join us for a special seminar on a problem derived from evolutionary biology.

    Date: Tuesday April 6th, 2004
    Time: 1:30-2:30 pm
    Room: CSE 691 (Gates Commons) (map: http://www.washington.edu/home/maps/southcentral.html?80,70,860,720)
    Speaker: Sagi Snir, Technion

    Title : Convex Recoloring of Strings and Trees

    Abstract : A coloring of a tree is convex if the vertices that
    pertain to any color induce a connected subtree; a partial coloring
    (which assigns colors to some of the vertices) is convex if it can be
    completed to a convex (total) coloring. Convex (partial) colorings
    of trees are closely related to areas such as phylogenetics,
    linguistics, etc. (a brief description of these relations will be
    given in the talk).

    When a coloring of a tree is not convex, it is desirable to know "how far"
    it is from a convex one. Few common measures for this are based on the
    parsimony score, which is the number of edges whose endpoints have
    different colors. These measures suffer from the inability to cope with
    partial coloring and do not estimate the distance to some convex coloring.
    In this talk we define and study another natural measure for this
    distance: the minimal number of vertices which need to be recolored to
    make the coloring convex. This can be viewed as minimizing the number of
    "exceptional vertices" w.r.t. to a convex coloring. We show that finding
    this distance is NP-hard even for strings. In the positive side we present
    few algorithms for optimal convex recoloring of strings and of trees that
    are practical in real life. Finally, we present efficient approximation
    algorithms for the problem.

    Joint work with Shlomo Moran

    _______________________________________________
    Theory-group mailing list
    Theory-group@cs.washington.edu
    http://mailman.cs.washington.edu/mailman/listinfo/theory-group


  • Next message: beame@cs.washington.edu: "Time & Room Change: CSE 590Z Theory Seminar"

    This archive was generated by hypermail 2.1.6 : Mon Mar 22 2004 - 11:32:47 PST