Two Problems in Computational Genomics

Simple item page
dc.contributor.authorBelal, Nahla Ahmeden
dc.contributor.committeechairHeath, Lenwood S.en
dc.contributor.committeememberAbdel-Hamid, Aymanen
dc.contributor.committeememberMurali, T. M.en
dc.contributor.committeememberGrene, Ruthen
dc.contributor.committeememberSetubal, João C.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T20:07:49Zen
dc.date.adate2011-03-22en
dc.date.available2014-03-14T20:07:49Zen
dc.date.issued2011-02-14en
dc.date.rdate2011-03-22en
dc.date.sdate2011-02-26en
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.en
dc.description.degreePh. D.en
dc.identifier.otheretd-02262011-120333en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-02262011-120333/en
dc.identifier.urihttp://hdl.handle.net/10919/26318en
dc.publisherVirginia Techen
dc.relation.haspartBelal_NA_D_2011.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjecthorizontal gene transferen
dc.subjectTwo Problems in Computational Genomicsen
dc.subjectwhole genome alignmenten
dc.subjectdynamic programmingen
dc.subjectGraph theoryen
dc.subjectbiology and geneticsen
dc.subjectgraph algorithmsen
dc.subjectpartial order setsen
dc.titleTwo Problems in Computational Genomicsen
dc.typeDissertationen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Belal_NA_D_2011.pdf
Size:
805.08 KB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations