Title: | The Consecutive-Ones Property Problem as a Model for Inferring Ancestral Genomes |
Speaker: |
Murray Patterson Department of Computer Science, University of British Columia |
Abstract |
While an extinct species cannot be sequenced, if we are given a
phylogeny tree containing this species we can reconstruct its genome
using the data from a set of its derived, extant species. This is
done by the following encoding of the genomic information of these
extant species in a binary matrix: each column of the matrix
represents a genomic marker (DNA sequence, etc.) that is believed to
have been present and unique in the considered unsequenced genome, and
each row of the matrix represents a set of markers that are believed
to have been contiguous along a chromosome of the unsequenced genome.
The goal is then to find one (or several if possible) total orders on
the markers that respect all rows (i.e., that keep all entries 1
together in each row). This is the combinatorial problem of
determining if this binary matrix has the Consecutive-Ones Property
(C1P). While determining if a matrix has the C1P can be done in linear
time, common problem in such applications is that matrices obtained
from experiments do not have the C1P, due to small errors in this
encoding. |