Friday, June 29, 2012 - 17:15 in V3-204
Linearization of ancestral chromosomal genomes
A talk in the
'FSPM-Kolloquium' series by
Jan Manuch from Simon Fraser University, Canada
| Abstract: |
Recovering the structure of ancestral genomes can be formalized in terms of the Consecutive-Ones Property (C1P) of binary matrices. The corresponding optimization problem asks to extract, from a given binary matrix, a maximum subset of rows that satisfy the C1P. This problem is in general intractable, in particular if the ancestral genome is expected to contain only linear chromosomes or a unique circular chromosome. In the present work, we consider a relaxation of these problems, which consists in allowing genomes that can contain several chromosomes, each either linear or circular.
We show that, when restricted to binary matrices of degree two (every row has at most two non zero entries), used in most ancestral genome reconstruction frameworks, the problem of recovering an ancestral genome with several
circular or linear chromosomes is polynomially solvable using a reduction to a matching problem. We also prove that for degree 3 matrices the problem is NP-complete, thus tracing sharp tractability boundaries.
Joint work with M. Patterson, R. Wittler, C. Chauve and E. Tannier. |
