Application of Combinatorial Optimization Techniques in Genomic Median Problems

Application of Combinatorial Optimization Techniques in Genomic Median Problems

Show full item record

Title: Application of Combinatorial Optimization Techniques in Genomic Median Problems
Author: Haghighi, Maryam
Abstract: Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.
Date: 2012
URI: http://hdl.handle.net/10393/20484
Supervisor: Boyd, Sylvia
Faculty: Sciences / Science
Degree: PhD

Files in this item

Files Size Format View
Haghighi_Maryam_2012_thesis.pdf 649.8Kb application/pdf View/Open

This item appears in the following Collection(s)

Show full item record


Contact information

Morisset Hall (map)
65 University Private
Ottawa ON Canada
K1N 6N5

Tel. 613-562-5800 (4563)
Fax 613-562-5195

ruor@uottawa.ca