Related Experiment Video
Updated: Jul 10, 2026

Novel Sequence Discovery by Subtractive Genomics
Published on: January 25, 2019
Exemplar longest common subsequence
Paola Bonizzoni1, Gianluca Della Vedova, Riccardo Dondi
1Dipartimento di Informatica, Sistemistica e Communicazione, Universitá degli Studi di Milano-Bicocca, Via Bicocca Degli, Arcimboldi, Milano, Italy. bonizzoni@disco.unimib.it
Abstract:
In this paper, we investigate the computational and approximation complexity of the Exemplar Longest Common Subsequence of a set of sequences (ELCS problem), a generalization of the Longest Common Subsequence problem, where the input sequences are over the union of two disjoint sets of symbols, a set of mandatory symbols and a set of optional symbols. We show that different versions of the problem are APX-hard even for instances with two sequences. Moreover, we show that the related problem of determining the existence of a feasible solution of the Exemplar Longest Common Subsequence of two sequences is NP-hard. On the positive side, we first present an efficient algorithm for the ELCS problem over instances of two sequences where each mandatory symbol can appear in total at most three times in the sequences. Furthermore, we present two fixed-parameter algorithms for the ELCS problem over instances of two sequences where the parameter is the number of mandatory symbols.
Related Concept Videos
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Multi-species Conserved Sequences
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Introduction to Sequences
Sequences
Arithmetic Sequences
Convergence of Sequences

