Type of Document	Dissertation
Author	Belal, Nahla Ahmed
Author's Email Address	nbelal@vt.edu
URN	etd-02262011-120333
Title	Two Problems in Computational Genomics
Degree	PhD
Department	Computer Science
Advisory Committee	Advisor Name Title Heath, Lenwood S. Committee Chair Abdel-Hamid, Ayman Committee Member Grene, Ruth Committee Member Murali, T. M. Committee Member Setubal, Joao Carlos Committee Member
Keywords	horizontal gene transfer Two Problems in Computational Genomics whole genome alignment dynamic programming Graph theory biology and genetics graph algorithms partial order sets
Date of Defense	2011-02-14
Availability	unrestricted
Abstract This work addresses two novel problems in the field of computational genomics. The first is whole genome alignment and the second is inferring horizontal gene transfer using posets. We define these two problems and present algorithmic approaches for solving them. For the whole genome alignment, we define alignment graphs for representing different evolutionary events, and define a scoring function for those graphs. The problem defined is proven to be NP-complete. Two heuristics are presented to solve the problem, one is a dynamic programming approach that is optimal for a class of sequences that we define in this work as breakable arrangements. And, the other is a greedy approach that is not necessarily optimal, however, unlike the dynamic programming approach, it allows for reversals. For inferring horizontal gene transfer, we define partial order sets among species, with respect to different genes, and infer genes involved in horizontal gene transfer by comparing posets for different genes. The posets are used to construct a tree for each gene. Those trees are then compared and tested for contradiction, where contradictory trees correspond to genes that are candidates of horizontal gene transfer.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    Belal_NA_D_2011.pdf 824.40 Kb 00:03:48 00:01:57 00:01:43 00:00:51 00:00:04

If you have questions or technical problems, please Contact DLA.