Applications of graph theory to chromosome rearrangements and phylogenetics

Graph theoretic and probabilistic methods are fast becoming indispensable to the field of computational biology, most notably in the study of DNA alterations. We will discuss two such applications: (1) determining aberration formation pathways from large scale DNA rearrangements, and (2) reconstructing evolutionary trees from DNA point mutations. Both applications have yielded computer implementations that allow for a more thorough and accurate analysis of experimental data. While large scale genome rearrangements occur in evolution, and while phylogenetic trees can be applied to the progeny of a radiation damaged cell, we will approach each application separately and in its original context.; Ionizing radiation may damage a cell by breaking both strands of DNA in multiple locations, essentially cutting chromosomes to pieces. The cell is equipped with enzymatic pathways to repair these breaks; however, these mechanisms are imperfect and may result in a large scale rearrangement of the genome. DNA staining techniques such as mFISH (multicolor fluorescent in situ hybridization) provide a means for analyzing repair/misrepair pathways by examining the observed final pattern. An mFISH pattern does not uniquely determine the entire exchange process that produced the aberration; however, assuming a minimum number of breaks, it is possible to generate a distribution of exchange processes consistent with free-end misrejoining. Further, experimentally produced aberration patterns may be incomplete; that is, there is no rearrangement that explains the observed pattern. We describe an algorithm for determining a distribution of aberration processes consistent with an incomplete observed final pattern.; We next approach the question of how to reconstruct the evolutionary history between a collection of extant species. The Neighbor-Joining algorithm is a recursive procedure for reconstructing trees that is based on a transformation of pairwise distances between leaves. We present a generalization of the neighbor-joining transformation, which uses estimates of weights of m-leaf subtrees rather than pairwise distances in the tree. This leads to an improved neighbor-joining algorithm whose total running time is still polynomial in the number of taxa. On simulated data, the method outperforms other distance-based methods, and in some cases improves over fastDNAml.