Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
2 results
Search Results
Item Computationally Comparing Biological Networks and Reconstructing Their Evolution(2012) Patro, Robert; Kingsford, Carleton L; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Biological networks, such as protein-protein interaction, regulatory, or metabolic networks, provide information about biological function, beyond what can be gleaned from sequence alone. Unfortunately, most computational problems associated with these networks are NP-hard. In this dissertation, we develop algorithms to tackle numerous fundamental problems in the study of biological networks. First, we present a system for classifying the binding affinity of peptides to a diverse array of immunoglobulin antibodies. Computational approaches to this problem are integral to virtual screening and modern drug discovery. Our system is based on an ensemble of support vector machines and exhibits state-of-the-art performance. It placed 1st in the 2010 DREAM5 competition. Second, we investigate the problem of biological network alignment. Aligning the biological networks of different species allows for the discovery of shared structures and conserved pathways. We introduce an original procedure for network alignment based on a novel topological node signature. The pairwise global alignments of biological networks produced by our procedure, when evaluated under multiple metrics, are both more accurate and more robust to noise than those of previous work. Next, we explore the problem of ancestral network reconstruction. Knowing the state of ancestral networks allows us to examine how biological pathways have evolved, and how pathways in extant species have diverged from that of their common ancestor. We describe a novel framework for representing the evolutionary histories of biological networks and present efficient algorithms for reconstructing either a single parsimonious evolutionary history, or an ensemble of near-optimal histories. Under multiple models of network evolution, our approaches are effective at inferring the ancestral network interactions. Additionally, the ensemble approach is robust to noisy input, and can be used to impute missing interactions in experimental data. Finally, we introduce a framework, GrowCode, for learning network growth models. While previous work focuses on developing growth models manually, or on procedures for learning parameters for existing models, GrowCode learns fundamentally new growth models that match target networks in a flexible and user-defined way. We show that models learned by GrowCode produce networks whose target properties match those of real-world networks more closely than existing models.Item Convergence of Adaptive Finite Element Methods(2005-12-05) Mekchay, Khamron; Nochetto, Ricardo H.; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We develop adaptive finite element methods (AFEMs) for elliptic problems, and prove their convergence, based on ideas introduced by D\"{o}rfler \cite{Dw96}, and Morin, Nochetto, and Siebert \cite{MNS00, MNS02}. We first study an AFEM for general second order linear elliptic PDEs, thereby extending the results of Morin et al \cite{MNS00,MNS02} that are valid for the Laplace operator. The proof of convergence relies on quasi-orthogonality, which accounts for the bilinear form not being a scalar product, together with novel error and oscillation reduction estimates, which now do not decouple. We show that AFEM is a contraction for the sum of energy error plus oscillation. Numerical experiments, including oscillatory coefficients and {both coercive and non-coercive} convection-diffusion PDEs, illustrate the theory and yield optimal meshes. The role of oscillation control is now more crucial than in \cite{MNS00,MNS02} and is discussed and documented in the experiments. We next introduce an AFEM for the Laplace-Beltrami operator on $C^1$ graphs in $R^d ~(d\ge2)$. We first derive a posteriori error estimates that account for both the energy error in $H^1$ and the geometric error in $W^1_\infty$ due to approximation of the surface by a polyhedral one. We devise a marking strategy to reduce the energy and geometric errors as well as the geometric oscillation. We prove that AFEM is a contraction on a suitably scaled sum of these three quantities as soon as the geometric oscillation has been reduced beyond a threshold. The resulting AFEM converges without knowing such threshold or any constants, and starting from any coarse initial triangulation. Several numerical experiments illustrate the theory. Finally, we introduce and analyze an AFEM for the Laplace-Beltrami operator on parametric surfaces, thereby extending the results for graphs. Note that, due to the nature of parametric surfaces, the geometric oscillation is now measured in terms of the differences of tangential gradients rather than differences of normals as for graphs. Numerical experiments with closed surfaces are provided to illustrate the theory.