Show simple item record

dc.contributor.authorBelal, Nahla Ahmeden_US
dc.date.accessioned2014-03-14T20:07:49Z
dc.date.available2014-03-14T20:07:49Z
dc.date.issued2011-02-14en_US
dc.identifier.otheretd-02262011-120333en_US
dc.identifier.urihttp://hdl.handle.net/10919/26318
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_US
dc.publisherVirginia Techen_US
dc.relation.haspartBelal_NA_D_2011.pdfen_US
dc.rightsI hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to Virginia Tech or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.en_US
dc.subjecthorizontal gene transferen_US
dc.subjectTwo Problems in Computational Genomicsen_US
dc.subjectwhole genome alignmenten_US
dc.subjectdynamic programmingen_US
dc.subjectGraph theoryen_US
dc.subjectbiology and geneticsen_US
dc.subjectgraph algorithmsen_US
dc.subjectpartial order setsen_US
dc.titleTwo Problems in Computational Genomicsen_US
dc.typeDissertationen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Scienceen_US
dc.contributor.committeechairHeath, Lenwood S.en_US
dc.contributor.committeememberAbdel-Hamid, Aymanen_US
dc.contributor.committeememberMurali, T. M.en_US
dc.contributor.committeememberGrene, Ruthen_US
dc.contributor.committeememberSetubal, João C.
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-02262011-120333/en_US
dc.date.sdate2011-02-26en_US
dc.date.rdate2011-03-22
dc.date.adate2011-03-22en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record