Campus Event Calendar
Event Entry
What and Who
Reconstructing a history of recombinations from a set of sequences
John Kececioglu
University of Arizona Department of Computer Science
Talk
AG 1, AG 2, AG 3, AG 4
MPI Audience
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 18 June 2003
10:30
-- Not specified --
46.1 - MPII
023
Saarbrücken
Abstract
One of the classic problems in biology is the reconstruction of evolutionary history. A recent trend in the area is to increase the explanatory power of the models that are considered by incorporating higher-order evolutionary events that more accurately reflect the mechanisms of mutation at the level of the chromosome.
We take a step in this direction by considering the problem of reconstructing an evolutionary history for a set of genetic sequences that have evolved by recombination. Recombination is a non-tree-like event that produces a child sequence by crossing two parent sequences .We present polynomial-time algorithms for reconstructing a parsimonious history of such events for several models of recombinations when all swquences, including those of ancestors, are present in the input. We also show that these models appear to be near the limit of what can be solved in polynomial time, in that several natural generalizations are NP-complete.
Contact
Jochen Maydt
--email hidden
passcode not visible
logged in users only