Algorithmic techniques for military and biological problems.
详细信息
文摘
In this dissertation we consider three problems which use algorithmic approaches from the graph theory field. In the first problem, we use Voronoi diagram and its dual graph Delaunay triangulation to solve three different versions of a well known computational geometry problem called minimum separating circle for bichromatic points. We first consider the kinetic version of the problem in which points are allowed to move along linear trajectories with constant speed. Given a set R containing n red points and a set B containing m blue points, we show that the locus of the minimum separating circle with one moving blue point has a complexity of Omn) and can be computed in Omn logmn)) time, the locus of the center of the minimum separating circle with a moving red point has complexity Onm2) and can be computed in Onm2 logm) time, and the locus of the center of the minimum separating circle with multiple moving points has complexity Om 2n2＋&epsi；) and can be found in Om2n2＋&epsi； logmn) ＋ mn3＋&epsi；) time, where &epsi； is an arbitrarily small positive constant. Then, we show that the minimum separating circle with a center on a given line can be computed in Om ＋ n) log m ＋ n)) ＋ O*m) 1.5) time, where the O* notation ignores some polylogarithmic factor. Next, we show that the optimal fixed radius separating circle problem with a radius given at a query time, can be solved in O* s)3) preprocessing and Olog s)) query time, where s ＝ n ＋ m.. In our second problem we utilize a graph theoretic data structure called Voronoi diagram for graphs aiming to come up with an efficient protein-protein interaction network clustering algorithm. For unweighted graphs, Voronoi diagram for graphs can be found in O|E|) time, whereas for weighed graphs the optimal running time is O| E| ＋ |V| log |V|), where | V| denotes the number of nodes and |E| denotes the number of edges in a graph. More specifically, we employ our algorithm in analyzing the erythrocyte interactome in an attempt to discover the influence that the currently incurable Sickle Cell Disease has on it. In addition, we have assembled the most up-to-date red blood cell interactome and created a software tool which can be used to analyze different types of large networks. Finally, we give an efficient algorithm for pairwise protein sequence alignment which utilizes the concept of graph rigidity. Our algorithm reduces the running time of optimal alignment algorithms, while it outperforms heuristic algorithms in terms of accuracy at the same time. The running time of our algorithm is Or &lowast； m), where r is the length of the largest rigid region in one of the two sequences and m is the length of the other sequence.