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.