We prove that the genome aliquoting problem, the problem of finding a recent polyploid ancestor of a genome, with breakpoint distance can be solved in polynomial time. We propose an aliquoting algorithm that is a 2-approximation for the genome aliquoting problem with double cut and join distance, improving upon the previous best solution to this problem, Feijão and Meidanis' 4-approximation algorithm.
Get full access to this article
View all access options for this article.
References
1.
AlekseyevM.A., PevznerP.A.2007. Whole genome duplications and contracted breakpoint graphs. SIAM J. Comput., 36:1748–1763.
2.
BergeronA., MixtackiJ., StoyeJ.2006. A unifying view of genome rearrangements. Lect. Notes Comput. Sci., 4175:163–173.
3.
El-MabroukN., SankoffD.2003. The reconstruction of doubled genomes. SIAM J. Comput., 32:754–792.
4.
FeijãoP., MeidanisJ.2009. SCJ: a novel rearrangement operation for which sorting, genome median and genome halving problems are easy. Lect. Notes Comput. Sci., 5724:85–96.
5.
LovászL., PlummerM.D.2009. Matching Theory. AMS Chelsea Publishing: Providence.
