Approximating the Minimum Breakpoint Linearization Problem for Genetic Maps without Gene Strandedness
The study of genetic map linearization leads to a combinatorial hard problem, called the {\em minimum breakpoint linearization} (MBL) problem. It is aimed at finding a linearization of a partial order which attains the minimum breakpoint distance to a reference total order. The approximation algorithms previously developed for the MBL problem are only applicable to genetic maps in which genes or markers are represented as signed integers. However, current genetic mapping techniques generally do not specify gene strandedness so that genes can only be represented as unsigned integers. In this paper, we study the MBL problem in the latter more realistic case. An approximation algorithm is thus developed, which achieves a ratio of $(m^2+2m-1)$ and runs in $O(n^7)$ time, where $m$ is the number of genetic maps used to construct the input partial order and $n$ the total number of distinct genes in these maps.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Singularity-Based Consistent QML Estimation of Multiple Breakpoints in High-Dimensional Factor Models
This paper investigates the estimation of high-dimensional factor models in which factor loadings undergo an unknown number of structural changes over time. Given that a model with multiple changes in factor loadings can…
Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs
Genome rearrangements can be modeled as $k$-breaks, which break a genome at k positions and glue the resulting fragments in a new order. In particular, reversals, translocations, fusions, and fissions are modeled as $2$-…
Rare recombination events generate sequence diversity among balancer chromosomes in Drosophila melanogaster
Multiply inverted balancer chromosomes that suppress exchange with their homologs are an essential part of the genetic toolkit in Drosophila melanogaster. Despite their widespread use, the organization of balancer chromo…
DiversityEvidence of epigenetic oncogenesis: a turning point in cancer research
In cancer research, the term epigenetics was used in the 1970s in its modern sense encompassing non-genetic events modifying the chromatin state, mainly to oppose the emerging oncogene paradigm. However, starting from th…
Improved identification of breakpoints in piecewise regression and its applications
Identifying breakpoints in piecewise regression is critical in enhancing the reliability and interpretability of data fitting. In this paper, we propose novel algorithms based on the greedy algorithm to accurately and ef…
regression