2021/10/06 by Rain Jiang, Kai Jiang, Jiang, Rain +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #DNA and Biological Computing #Genome Rearrangement Algorithms #cs.CC #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2110.02809
arxiv created 2021/10/06 · arxiv updated 2021/10/07
Linearizing two partial orders to maximize the number of adjacencies and minimize the number of breakpoints is APX-hard. This holds even if one of the two partial orders is already a linear order and the other is an interval order, or if both partial orders are weak orders.