Balanced vertices in trees and a simpler algorithm to compute the genomic distance (Q607155)

The \textit{genomic distance problem} in the Hannenhalli-Pevzner theory is the following: Given two genomes whose chromosomes are linear, calculate the minimum number of translocations, fusions, fissions and inversions that transform one genome into the other. The paper provides a short and transparent solution for the covering cost of white-grey trees which play a crucial role in the algorithm of \textit{A. Bergeron}, \textit{J. Mixtacki}, and \textit{J. Stoye} [``A new linear time algorithm to compute the genomic distance via the double cut and join distance,'' Theor. Comput. Sci. 410, No.\,51, 5300--5316 (2009; Zbl 1186.68144)] to compute the rearrangement distance between two multichromosomal genomes in linear time. The algorithm utilizes a new notion, the balanced vertex, that provides an analogy of the center of the tree.