Narrow Results

We present some experiences with the problem of multiple genome comparison, analogous to multiple sequence alignment in sequence comparison, under the inversion and transposition distance metrics, given a fixed phylogeny. We first describe a heuristic for the case in which phylogeny is a star on three vertices and then use this to approximate the multiple genome comparison problem via local search.

Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case.

Many models of genome rearrangement involve operations that are self-inverse, and hence generate a group acting on the space of genomes. This gives a correspondence between genome arrangements and the elements of a group, and consequently, between evolutionary paths and walks on the Cayley graph. Many common methods for phylogenetic reconstruction rely on calculating the minimal distance between two genomes; this omits much of the other information available from the Cayley graph. In this paper, we begin an exploration of some of this additional information, in particular describing the phylogeny as a Steiner tree within the Cayley graph, and exploring the “interval” between two genomes. While motivated by problems in systematic biology, many of these ideas are of independent group-theoretic interest.