Student Research Profiles

Julian Sahasrabudhe (2011)	Niamh Chaparro (2010)	Aleks Vlasev (2010)	Bill Bao (2009)	Asif Zaman (2009)	Ryan Coghlan (2009)	Steve Melczer (2009)

On the 1-Consecutive Ones Property and the Reconstruction of Possible Ancestral Genomes

Ryan Coghlan Mathematics Major

Saehee Choi  Industrial Mathematics Major (co-researcher but not an NSRC USRA participant)

Supervisor: Tamon Stephen, Cedric Chauve

Finding the genetic sequences of extinct animals is a longstanding problem in genetics, one compounded by the fact DNA decays over time until it is eventually no longer reliable. Due to this even if DNA samples of long extinct animals are found, one cannot reliably sequence their DNA. One possible way to get around this problem is to reconstruct these DNA sequences, or ancestral genomes, by comparing the DNA of the extinct animal's ancestors.

We describe a reconstruction technique that relies on a property of binary matrices called the Consecutive Ones' Property. A matrix has the Consecutive Ones' Property if there is an arrangement of its columns such that all the ones in each row are consecutive. By converting a set of candidate genomes to a binary matrix and using optimization techniques which rely on this property, we are then able to construct all possible ancestral genomes for the extinct species. In our work we extend these previous algorithms to the case where in a given row a single zero may appear between any two ones, allowing the algorithms to be run on new and higher resolution DNA sequences. Using these techniques we then reconstructed the DNA sequences for various mammalian ancestors.