Detecting the interleaving relationship between sequences has become impor- tant because of its wide applications to genomic and signal comparison. Given a target sequence T and two merging sequences A and B, recently Huang et al. propose algo- rithms for the merged LCS problem, without or with block constraint, whose aim is to find the longest common subsequence (LCS) with interleaving relationship. Without block constraint, Huang’s algorithm requires O(nmr)-time and O(mr)-space, where n = |T|, m and r denote the longer and shorter length of A and B, respectively. In this paper, for solving the problem without block constraint, we first propose an algorithm with O(Lnr) time and O(m + Lr) space. We also propose an algorithm to solve the problem with block constraint. Our algorithms are more efficient than previous results, especially for sequences over large alphabets.
int MLCS_PengSparse(vector< int> T, vector< int> A, vector< int>B, int Tlen, int Alen, int Blen, int size)
{
vector< vector< int>> nextA(size + 1, vector< int>(Alen + 1, 0));
vector< vector< int>> nextB(size + 1, vector< int>(Blen + 1, 0));
int len = 1;
vector< vector< triple>> QL1(Tlen + 2, vector< triple>());
vector< vector< triple>> QL2(Tlen + 2, vector< triple>());
vector< vector< triple>> tempQL(Tlen + 2, vector< triple>());
int qlsize = 0;
int locationA = 0;
int locationB = 0;
//construct array of nextA
for (int i = 1; i <= size; ++i) {
locationA = Alen + 1;
for (int j = Alen; j > 0; --j) {
if (j == Alen)
nextA[i][j] = locationA;
if (A[j] == i) {
locationA = j;
nextA[i][j - 1] = locationA;
}
else {
nextA[i][j - 1] = locationA;
}
}
}
//construct array of nextB
for (int i = 1; i <= size; ++i) {
locationB = Blen + 1;
for (int j = Blen; j > 0; --j) {
if (j == Blen)
nextB[i][j] = locationB;
if (B[j] == i) {
locationB = j;
nextB[i][j - 1] = locationB;
}
else {
nextB[i][j - 1] = locationB;
}
}
}
int PosA = 0;
int PosB = 0;
int layer = 1;
while (1) {
if (layer % 2 == 1) {
QL1[0].push_back(triple(0, 0));
for (int l = 1; l <= len; l++)
{
for (auto mytriple = QL2[l - 1].begin(); mytriple != QL2[l - 1].end(); ++mytriple)
{
PosA = nextA[T[layer - 1]][mytriple->x];
PosB = nextB[T[layer - 1]][mytriple->y];
if (PosA <= Alen) {
QL1[l].push_back(triple(PosA, mytriple->y));
}
if (PosB <= Blen) {
QL1[l].push_back(triple(mytriple->x, PosB));
}
}
if (QL2[l].size() > 0) {
for (auto mytriple = QL2[l].begin(); mytriple != QL2[l].end(); ++mytriple)
{
QL1[l].push_back(triple(mytriple->x, mytriple->y));
}
}
//2-D minima algorithm
qlsize = QL1[l].size();
if (qlsize > 1) {
for (int i = 0; i < qlsize; ++i) {
triple temptri = QL1[l][i];
if (!tempQL[temptri.x].empty() && temptri.y < tempQL[temptri.x][0].y) {
tempQL[temptri.x].erase(tempQL[temptri.x].begin());
tempQL[temptri.x].push_back(temptri);
}
else if (tempQL[temptri.x].empty() == true) {
tempQL[temptri.x].push_back(temptri);
}
}
QL1[l].clear();
int prevMaxY = Blen + 1;
for (int i = 0; i <= Alen; ++i) {
if (!tempQL[i].empty()) {
if (tempQL[i][0].y < prevMaxY) {
prevMaxY = tempQL[i][0].y;
QL1[l].push_back(tempQL[i][0]);
}
tempQL[i].clear();
}
}
}
}//end for j
if (QL1[len].size() > 0)
len++;
if (layer == Tlen + 1)
break;
++layer;
}
else {
QL2[0].push_back(triple(0, 0));
for (int l = 1; l <= len; l++)
{
for (auto mytriple = QL1[l - 1].begin(); mytriple != QL1[l - 1].end(); ++mytriple)
{
PosA = nextA[T[layer - 1]][mytriple->x];
PosB = nextB[T[layer - 1]][mytriple->y];
if (PosA <= Alen) {
QL2[l].push_back(triple(PosA, mytriple->y));
}
if (PosB <= Blen) {
QL2[l].push_back(triple(mytriple->x, PosB));
}
}
if (QL1[l].size() > 0) {
for (auto mytriple = QL1[l].begin(); mytriple != QL1[l].end(); ++mytriple)
{
QL2[l].push_back(triple(mytriple->x, mytriple->y));
}
}
//2-D minima algorithm
qlsize = QL2[l].size();
if (qlsize > 1) {
for (int i = 0; i < qlsize; ++i) {
triple temptri = QL2[l][i];
if (!tempQL[temptri.x].empty() && temptri.y < tempQL[temptri.x][0].y) {
tempQL[temptri.x].erase(tempQL[temptri.x].begin());
tempQL[temptri.x].push_back(temptri);
}
else if (tempQL[temptri.x].empty() == true) {
tempQL[temptri.x].push_back(temptri);
}
}
QL2[l].clear();
int prevMaxY = Blen + 1;
for (int i = 0; i <= Alen; ++i) {
if (!tempQL[i].empty()) {
if (tempQL[i][0].y < prevMaxY) {
prevMaxY = tempQL[i][0].y;
QL2[l].push_back(tempQL[i][0]);
}
tempQL[i].clear();
}
}
}
}//end for j
if (QL2[len].size() > 0)
len++;
if (layer == Tlen + 1)
break;
++layer;
}
}
return len - 1;
}