Near-medians that avoid the corners; a combinatorial probability approach

BMC Genomics

Research

David Sankoff¹  Chunfang Zheng¹  Caroline Anne Larlee¹ 

[1] Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, K1N 6N5, Ottawa, Canada;

关键词: median problem;    breakpoint distance;    combinatorial probabilities;   

DOI  :  10.1186/1471-2164-15-S6-S1

来源: Springer

【 摘 要 】

BackgroundThe breakpoint median for a set of k ≥ 3 random genomes tends to approach (any) one of these genomes ("corners") as genome length increases, although there are diminishing proportion of medians equidistant from all k ("medians in the middle"). Algorithms are likely to miss the latter, and this has consequences for the general case where input genomes share some or many gene adjacencies, where the tendency for the median to be closer to one input genome may be an artifact of the corner tendency.ResultsWe present a simple sampling procedure for constructing a "near median" that represents a compromise among k random genomes and that has only a slightly greater breakpoint distance to all of them than the median does. We generalize to the realistic case where genomes share varying proportions of gene adjacencies. We present a supplementary sampling scheme that brings the constructed genome even closer to median status.ConclusionsOur approach is of particular use in the phylogenetic context where medians are repeatedly calculated at ancestral nodes, and where the corner effect prevents different parts of the phylogeny from communicating with each other.

【 授权许可】

Unknown   
© Larlee et al.; licensee BioMed Central Ltd. 2014. This article is published under license to BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.