TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 14.11.2013


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.

14.11.2013 16:15
Laurent Bulteau
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe