Date of Award

1-1-2012

Document Type

Campus Access Dissertation

Department

Computer Science and Engineering

First Advisor

Jijun Tang

Abstract

This work investigates transforming scientific computing problems such as phylogenetic analysis, system simulation into abstract graph problems and developing algorithms for optimization. First, we investigate an efficient algorithm for unequal genome phylogeny reconstruction. Currently few methods can solve the median problem for unequal genomes which is essential in evolution tree and ancestral genome reconstruction. We present a new distance measurement model for unequal genomes and develop a branch-and-bound algorithm based on multiple breakpoint graph to calculate the median for unequal genomes. We also present a mixture method to infer the ancestral gene order based on maximum likelihood approach and adequate graph median solver. The median solver is extremely time consuming under high rearrangement rate compared with maximum likelihood approach but it gives better accuracy. So our mixture method aims to increase both the speed and accuracy for ancestral genome reconstruction. We also investigate the method to improve the simulation problem for large systems. The Modified Nodal Analysis (MNA) simulation method is widely used to solve electrical system networks. It has the disadvantage that the simulation time increases disproportionally with system size. To accelerate the simulation, latency insertion method has been introduced to partition the original system into a number of smaller sub-systems so that computation will be reduced. But so far there is no automatic method to optimally exploit the existing latency in the system. Our work focuses on an algorithm based on graph search to optimally activate the optional latency decouplers in the network. With the optimal activation, the system is partitioned in the way that maximum simulation speed up will be achieved.

Rights

© 2012, Yiwei Zhang

Download

Share

COinS