APPROXIMATION ALGORITHMS FOR THE MEDIAN PROBLEM IN THE BREAKPOINT MODEL Itsik Pe'er Department of Computer Science Tel Aviv University izik@math.tau.ac.il Ron Shamir Department of Computer Science Tel Aviv University shamir@math.tau.ac.il Abstract The problem of genome rearrangement is central in computational molecular biology. In order to infer the evolutionary history of three species based on their gene orders, one seeks a forth median species with gene order that minimizes the total distance to the former three. We study the problem using the number of breakpoints as a distance measure between permutations. We give several polynomial time approximation algorithms for the median problem on three and four signed permutations. The best algorithm we provide for three species guarantees an approximation ratio of~$7 \over 6$.