DCJ Path Formulation for Genome Transformations which Include Insertions, Deletions, and Duplications

摘要

For the case of insertions and deletions, with linear as well as circular chromosomes, we suggest permitting a “nugh” (half ghost, half null), which can shorten the distance. We give algorithms for the optimal closure, with and without nughs, and give the resulting distance formula in terms of paths. For certain simplest cases, we calculate the number of optimal ways to close the graph.