Back to search

University of Victoria (Canada)

Sorting signed permutations by transpositions and reversals

Abstract

dc:description.abstract

Large scale comparative genetic mapping offers exciting prospects for understanding genomic evolution and has recently become of interest in computational molecular biology. The genome rearrangement problem is the computational problem of determining the smallest number of evolutionary events required to transform a given genome into another. In this thesis, we study a specific variant of the genome rearrangement problem. We assume that every genome has exactly one linear chromosome, and that each gene is an oriented unit and appears exactly once per genome. Furthermore, our model allows only two kinds of evolutionary events: reversals and transpositions. The problem is equivalent to the problem of sorting signed permutations by transpositions and reversals. We explore the characteristics of signed permutations and their sorting path. This exploration results in lower and upper bounds for a shortest sorting path. These bounds help us develop three approximation algorithms. We also prove that sorting by transpositions and reversals is at least as hard as the problem sorting by transpositions only - the complexity of which is unknown. In an effort to implement an algorithm to find an optimal sorting path of events, we designed four techniques to reduce the input size of the problem and thus achieve an improvement of the actual running time for any exhaustive algorithm.

Degree

thesis:*
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Fei.
Advisors dc:contributor.supervisor
  • Stege, Ulrike
  • Müller, Hausi A.

Subjects

dc:subject × 2

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/524

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhang, Fei.. Sorting signed permutations by transpositions and reversals. 2008. http://hdl.handle.net/1828/524