Ryan Coghlan

NSERC Award holder
SFU undergraduate student, Mathematics Major

 

 

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

NSERC Project: Algorithms for the Gapped-C1P (Supervisors: 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.