Sets of medians in the non-geodesic pseudometric space of unsigned genomes with breakpoints

BMC Genomics

Research

Aryo Jamshidpey¹  David Sankoff²  Arash Jamshidpey² 

[1] Department of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences, 45195-1159, Gava Zang, Zanjan, Iran;Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, K1N 6N5, Ottawa, Canada;

关键词: breakpoint distance;    pseudometric;    non-geodesic space;    random genomes;   

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

来源: Springer

【 摘 要 】

BackgroundThe breakpoint median in the set Sn of permutations on n terms is known to have some unusual behavior, especially if the input genomes are maximally different to each other. The mathematical study of the set of medians is complicated by the facts that breakpoint distance is not a metric but a pseudo-metric, and that it does not define a geodesic space.ResultsWe introduce the notion of partial geodesic, or geodesic patch between two permutations, and show that if two permutations are medians, then every permutation on a geodesic patch between them is also a median. We also prove the conjecture that the input permutations themselves are medians.

【 授权许可】

Unknown   
© Jamshidpey 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.