skip to content
 

Reconstruction of certain normal networks from the genomes at leaves

Presented by: 
SJ Willson [Iowa]
Date: 
Tuesday 9th October 2007 - 14:00 to 15:00
Venue: 
INI Seminar Room 2
Abstract: 

A network N is a rooted acyclic directed graph. A base-set X for N is a subset of vertices including the root (or outgroup), all leaves, and all vertices of outdegree 1. A simple model of evolution is considered in which all characters are binary and in which back-mutations occur only at hybrid vertices. It is assumed that the genome is known for each member of the base-set X. If the network is known and is assumed to be "normal," then it is proved that the genome of every vertex is uniquely determined and can be explicitly reconstructed. Under additional hypotheses involving time-consistency and separation of the hybrid vertices, the network itself can also be reconstructed from the genomes of all members of X. An explicit polynomial-time procedure is described for performing the reconstruction.

University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons