### Page Content

### to Navigation

## Graph-based Approach for Optimally Linearizing a Partial Order into a Permutation

**Laurent Bulteau (TU Berlin)**

The NP-hard Minimum Breakpoint Linearization problem originates from comparative genomics. It aims at upgrading a partial order into a total order, by using as many consecutive pairs of a permutation as possible. For a biologist, it can be used to construct the total order of the genes on a chromosome if experiments only output a partial order but a complete order for the corresponding chromosome in a related species is known. We present a graph formulation which allows to reduce this problem to a variant of Feedback Vertex Set. We also investigate a parameterization of this problem using the number of so-called genomic maps used to create the input partial order. We show how this number may help yield an approximation algorithm for this problem.

Date | Speaker | Location | Language |
---|---|---|---|

14.11.2013 16:15 | Laurent Bulteau | TEL 512 | english |