Abstract
dc:description.abstractThis 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.
Degree
thesis:*- Name thesis:degree_name
- Ph. D.
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Virginia Tech
- Year dc:date.issued
- 2011
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Belal, Nahla Ahmed
- Chair dc:contributor.committeechair
-
- Heath, Lenwood S.
- Committee members dc:contributor.committeemember
-
- Abdel-Hamid, Ayman
- Murali, T. M.
- Grene, Ruth
- Setubal, João C.
Subjects
dc:subject × 8Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Licence dc:rights.uri
Identifiers
dc:identifier.*- Dc Identifier Other
- etd-02262011-120333
- OAI identifier oai:identifier
- oai:vtechworks.lib.vt.edu:10919/26318