An approximation algorithm for the minimum breakpoint linearization problem.
In the recent years, there has been a growing interest in inferring the total order of genes or markers on a chromosome, since current genetic mapping efforts might only suffice to produce a partial order. Many interesting optimization problems were thus formulated in the framework of genome rearrangement. As an important one among them, the minimum breakpoint linearization (MBL) problem is to find the total order of a partially ordered genome that minimizes its breakpoint distance to a reference genome whose genes are already totally ordered. It was previously shown to be NP-hard, and the algorithms proposed so far are all heuristic. In this paper, we present an {m(2)+m/2}-approximation algorithm for the MBL problem, where m is the number of gene maps that are combined together to form a partial order of the genome under investigation.
Chen
Xin
X
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore. chenxin@ntu.edu.sg
Cui
Yun
Y
D000465:Algorithms; D002874:Chromosome Mapping; D015321:Gene Rearrangement; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic