Balanced vertices in trees and a simpler algorithm to compute the genomic distance (Q607155)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Balanced vertices in trees and a simpler algorithm to compute the genomic distance |
scientific article |
Statements
Balanced vertices in trees and a simpler algorithm to compute the genomic distance (English)
0 references
19 November 2010
0 references
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.
0 references
rooted tree
0 references
comparative genomics
0 references
genome rearrangement
0 references