Pubblicazioni Aperte DIgitali Sapienza >
Scienze statistiche >
RICERCA OPERATIVA >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10805/2239

Title:  OPERATIONS RESEARCH: FROM COMPUTATIONAL BIOLOGY TO SENSOR NETWORK 
Authors:  DE COLA, MARIA 
Tutor:  FELICI, GIOVANNI 
Keywords:  EDGECOLORED GRAPH LONGEST PATH PROBLEMS GRAPH EMBEDDING TERTIARY STRUCTURE ELUCIDATION 
Issue Date:  18Nov2013 
Abstract:  In this dissertation we discuss the deployment of combinatorial optimization methods for modeling and solve real life problemS, with a particular emphasis to two biological problems arising from a common scenario: the reconstruction of the threedimensional shape of a biological molecule from Nuclear Magnetic Resonance (NMR) data.
The fi rst topic is the 3D assignment pathway problem (APP) for a RNA molecule.
We prove that APP is NPhard, and show a formulation of it based on edgecolored
graphs. Taking into account that interactions between consecutive nuclei in the NMR
spectrum are diff erent according to the type of residue along the RNA chain, each color
in the graph represents a type of interaction. Thus, we can represent the sequence of interactions as the problem of fi nding a longest (hamiltonian) path whose edges follow a given order of colors (i.e., the orderly colored longest path). We introduce three alternative IP formulations of APP obtained with a max flow problem on a directed graph with packing constraints over the partitions, which have been compared among themselves. Since the last two models work on cyclic graphs, for them we proposed an algorithm based on the solution of their relaxation combined with the separation of cycle inequalities in a Branch & Cut scheme.
The second topic is the discretizable distance geometry problem (DDGP), which is
a formulation on discrete search space of the wellknown distance geometry problem
(DGP). The DGP consists in seeking the embedding in the space of a undirected graph, given a set of Euclidean distances between certain pairs of vertices. DGP has two important applications: (i) fi nding the three dimensional conformation of a molecule from a subset of interatomic distances, called Molecular Distance Geometry Problem, and (ii) the Sensor Network Localization Problem. We describe a Branch & Prune (BP) algorithm
tailored for this problem, and two versions of it solving the DDGP both in protein
modeling and in sensor networks localization frameworks. BP is an exact and exhaustive
combinatorial algorithm that examines all the valid embeddings of a given weighted
graph G=(V,E,d), under the hypothesis of existence of a given order on V. By
comparing the two version of BP to wellknown algorithms we are able to prove the
e fficiency of BP in both contexts, provided that the order imposed on V is maintained. 
URI:  http://hdl.handle.net/10805/2239 
Appears in PhD:  RICERCA OPERATIVA

Files in This Item:
File 
Description 
Size  Format 
PhDThesisDeCola.pdf   3.28 MB  Adobe PDF   

This item is protected by original copyright

Items in PADIS are protected by copyright, with all rights reserved, unless otherwise indicated.
