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 O(mn) and can be computed in O(mn log(mn)) time, the locus of the center of the minimum separating circle with a moving red point has complexity O(nm2) and can be computed in O(nm2 logm) time, and the locus of the center of the minimum separating circle with multiple moving points has complexity O(m 2n2+ε) and can be found in O(m2n2+ε log(mn) + mn3+ε) time, where ε 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 O((m + 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 O(log( 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 O(r ∗ 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.