On the Complexity of Minimum Labeling Alignment of Two Genomes
  In this note we investigate the complexity of the Minimum Label Alignment problem and we show that such a problem is APX-hard. 
Riccardo Dondi, Nadia El-Mabrouk
cs.CC cs.DS q-bio.GN