Genome rearrangement problems accounting for duplicate genes

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2018-08-10
Authors/Contributors
Author: Mane, Aniket
Abstract
We investigate certain genome rearrangement problems studied in relation to genome evolution. We introduce the SCJ-TD-FD rearrangement model to explain the directed evolution from an ancestor A to a descendant D, where D may contain multiple copies of genes from A. We study the pairwise genome distance problem that aims at finding the most parsimonious sequence of cuts, joins and single-gene duplications that transforms A to D, under this model. Next, we study the rooted median problem under the SCJ-TD-FD model, for which the problem is shown to be NP-hard. We provide an Integer Linear Program that, on simulated data, predicts an optimal median with high accuracy. Finally, we study the Small Parsimony Problem under the SCJ-TD-FD model that aims at finding the gene orders at the internal nodes of a given species tree. We define an ILP-based approach to reconstruct the ancestral gene orders and present our experiments on a data-set of Anopheles mosquito genomes.
Document
Identifier
etd19786
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Chauve, Cedric
Member of collection
Attachment Size
etd19786.pdf 1.74 MB