Degree Type

Dissertation

Date of Award

2004

Degree Name

Doctor of Philosophy

Department

Theses & dissertations (Interdisciplinary)

Major

Bioinformatics and Computational Biology; Genetics;

First Advisor

Xun Gu

Second Advisor

Zhijun Wu

Abstract

Multiple genome rearrangement by signed reversal is discussed: For a collection of genomes represented by signed permutations, reconstruct their evolutionary history by using signed reversals, i.e. find a bifurcating tree where sampled genomes are assigned to leaf nodes and ancestral genomes (i.e. signed permutations) are hypothesized at internal nodes such that the total reversal distance summed over all edges of the tree is minimized. It is equivalent to finding an optimal Steiner tree that connects the given genomes by signed reversal paths. The key for the problem is to reconstruct all optimal Steiner nodes/ancestral genomes.;The problem is NP-hard and can only be solved by efficient approximation algorithms. Various algorithms/programs have been designed to solve the problem, such as BPAnalysis, GRAPPA, grid search algorithm, MGR greedy split algorithm (Chapter 1). However, they may have expensive computational costs or low inference accuracy. In this thesis, several new algorithms are developed, including nearest path search algorithm (Chapter 2), neighbor-perturbing algorithm (Chapter 3), branch-and-bound algorithm (Chapter 3), perturbing-improving algorithm (Chapter 4), partitioning algorithm (Chapter 5), etc. With theoretical proofs, computer simulations, and biological applications, these algorithms are shown to be 2-approximation algorithms and more efficient than the existing algorithms.

DOI

https://doi.org/10.31274/rtd-180813-12576

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu

Copyright Owner

Shiquan Wu

Language

en

Proquest ID

AAI3158380

File Format

application/pdf

File Size

88 pages

Share

COinS