Balanced vertices in trees and a simpler algorithm to compute the genomic distance |
| |
Authors: | Péter L Erdős Lajos Soukup Jens Stoye |
| |
Institution: | 1. Alfréd Rényi Institute of Mathematics, Budapest, P.O. Box 127, H-1364, Hungary;2. Universität Bielefeld, Technische Fakultät, AG Genominformatik, 33594 Bielefeld, Germany |
| |
Abstract: | This paper provides a short and transparent solution for the covering cost of white–grey trees which play a crucial role in the algorithm of Bergeron et al. to compute the rearrangement distance between two multichromosomal genomes in linear time (A. Bergeron, J. Mixtacki, J. Stoye, A new linear time algorithm to compute the genomic distance via the double cut and join distance, Theor. Comput. Sci. 410 (2009) 5300–5316). In the process it introduces a new center notion for trees, which seems to be interesting on its own. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|