Pisin yhteinen osajono (LCS) on tyy­pil­li­nen ongelma tie­to­tek­nii­kas­sa. LCS-ongelman rat­kai­su­ta­po­ja kysytään usein oh­jel­moi­jien haas­tat­te­luis­sa ja al­go­rit­mi­kurs­seil­la.

Mikä on pisin yhteinen alijono?

Ta­voit­tee­na on löytää kahden se­kvens­sin pisin yhteinen ali­se­kvens­si. Ali­se­kvens­si on johdettu se­kvens­sis­tä. Ali­se­kvens­sil­lä on sama ele­ment­tien järjestys, joissakin ta­pauk­sis­sa ele­ment­te­jä pois­te­taan. Kat­so­taan­pa muutamia esi­merk­ke­jä, jotta ym­mär­räm­me pe­ri­aa­tet­ta paremmin:

Sekvenssi X Sekvenssi Y LCS(X, Y)
FATHER MATTER ATER
MOTHER HERBAL HER
DAVID DANIEL DAI
Huomio

Pisin yhteinen alijono ja pisin yhteinen osajono eroavat toi­sis­taan mer­kit­tä­väs­ti, sillä os­ajo­nos­sa ei saa olla aukkoja. Esi­mer­kis­sä ”DAVID” ja ”DANIEL” pisin yhteinen osajono olisi ”DA”, koska ”I” on erotettu ”V”:llä ja ”N”:llä.

Onko LCS-on­gel­mas­ta käytännön esi­merk­ke­jä?

Pisin yhteinen osajono -ongelma on tärkeä kysymys kaikilla aloilla, joilla käytetään toi­sis­taan johtuvia jonoja. On olemassa tiettyjä tapoja löytää LCS, jotta voidaan selvittää, onko jonoissa yh­tä­läi­syyk­siä tai eroja, ja siten havaita mah­dol­li­set pla­gioin­nit. Tunnettu diff-apuoh­jel­ma, joka tarkistaa läh­de­teks­ti­tie­dos­to­jen muutokset, perustuu LCS-ongelmaan.

Bioin­for­ma­tii­kas­sa pisin yhteinen alijono-ongelma käytetään usein DNA-se­kvens­sien ana­ly­soin­nis­sa. DNA-emäkset muuttuvat ajan myötä tietyissä kohdissa mu­taa­tioi­den vuoksi. Pitkän yhteisen alijonon esiin­ty­mi­nen kahdessa se­kvens­sis­sä viittaa ge­neet­ti­seen su­ku­lai­suu­teen. Tämän avulla voimme jäljittää lajien välisen evo­luu­tion ge­neet­ti­sen ke­hi­tyk­sen ansiosta.

Kie­li­tie­tei­li­jät voivat myös käyttää pisimmän yhteisen osajonon ongelmaa tut­kiak­seen kielten kehitystä vuo­si­sa­to­jen ajan. Jos sinulla on kaksi eri kielistä peräisin olevaa sanaa, joilla on sama merkitys ja pitkä yhteinen osajono, se viittaa siihen, että niillä on sama juuri ja ety­mo­lo­gia. Tätä voi­tai­siin sitten pitää sa­man­lai­se­na his­to­rial­li­se­na ke­hi­tyk­se­nä.

Mitkä ovat ratkaisut pisimpään yhteiseen alijono-ongelmaan?

En­sin­nä­kin voit ratkaista LCS-ongelman naiivilla lä­hes­ty­mis­ta­val­la. Tämä on yk­sin­ker­tai­nen lä­hes­ty­mis­ta­pa, jossa ei käytetä op­ti­moin­te­ja tai erityisiä me­ne­tel­miä. Tätä varten lasket vain kaikki kahden se­kvens­sin ali­se­kvens­sit ja etsit pisimmän yhteisen ali­se­kvens­sin. Va­li­tet­ta­vas­ti tämä lä­hes­ty­mis­ta­pa ei ole kovin tehokas, joten se sopii vain lyhyille se­kvens­seil­le.

Alla on kolme tehokasta ratkaisua LCS-ongelmaan:

  1. Re­kur­sii­vi­nen lä­hes­ty­mis­ta­pa
  2. Op­ti­moin­ti muis­ta­mi­sen avulla
  3. Dy­naa­mi­nen oh­jel­moin­ti

Kaikille lä­hes­ty­mis­ta­voil­le on yhteistä, että ne eroavat toi­sis­taan kolmessa ta­pauk­ses­sa näiden kahden se­kvens­sin osalta:

  • Viimeinen kirjain on sama.
  • Viimeinen kirjain ei ole sama.
  • Toisen merk­ki­jo­non pituus on nolla.

Lä­hes­ty­mis­ta­vat eroavat toi­sis­taan ajan­käy­tön mo­ni­mut­kai­suu­den (asymp­to­ti­nen suo­ri­tusai­ka) ja ti­lan­käy­tön mo­ni­mut­kai­suu­den (muistin käyttö) suhteen:

Lä­hes­ty­mis­ta­pa Kesto Muisti
Naiivi lä­hes­ty­mis­ta­pa O(n * n²) O(n)
Re­kur­sii­vi­nen lä­hes­ty­mis­ta­pa O(n²) O(1)
Op­ti­moin­ti muis­ta­mi­sen avulla O(n * m) O(n * m)
Dy­naa­mi­nen oh­jel­moin­ti O(n * m) O(n * m)
Huomio

Alla esitetyt al­go­rit­mit laskevat kaikki pisimmän yhteisen osajonon pituuden. Tar­vit­taes­sa on olemassa useita tämän pituisia osajonoja, jotka voidaan määrittää muiden vaiheiden avulla.

Pisin yhteinen ali­jo­no­jen re­kur­sii­vi­nen mää­rit­tä­mi­nen

Jos tar­kas­tel­laan LCS-ongelmaa, voidaan havaita, että sillä on ”op­ti­maa­li­nen ali­ra­ken­ne”. Tämä tar­koit­taa, että ongelma voidaan jakaa osion­gel­miin. Rat­kai­su­na voidaan käyttää re­kur­sii­vis­ta lä­hes­ty­mis­ta­paa. Alla on esi­merk­ke­jä al­go­rit­meis­ta, joilla tämä voidaan toteuttaa kolmella ylei­sim­mäl­lä oh­jel­moin­ti­kie­lel­lä.

Python

def lcs(X, Y, m, n):
  # Base case
  if m == 0 or n == 0:
    return 0
  # Last elements are equal
  elif X[m-1] == Y[n-1]:
    return 1 + lcs(X, Y, m-1, n-1)
  # Last elements differ
  else:
    return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))

# Let's test
X, Y = "DANIEL", "DAVID"
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
python

Java

import java.io.*;

class LCS {
  public static int lcs(String A, String B, int m, int n)
  {
    // Base case
    if (m == 0 || n == 0)
      return 0;
    // Last elements are equal
    if (A.charAt(m - 1) == B.charAt(n - 1))
      return 1 + lcs(A, B, m - 1, n - 1);
    // Last elements differ
    else
      return Math.max(lcs(A, B, m, n - 1),
       lcs(A, B, m - 1, n));
  }
  
  // Let's test
  public static void main(String[] args)
    {
      String X = "DAVID";
      String Y = "DANIEL";
      int lcsLength = LCS.lcs(X, Y, X.length(), Y.length());
      System.out.println("Length of LCS is: " + lcsLength);
    }
}
java

C++

#include <iostream>
using namespace std;

int lcs(string X, string Y, int m, int n)
{
  // Base case
  if (m == 0 || n == 0) {
    return 0;
  }
  // Last elements are equal
  if (X[m - 1] == Y[n - 1]) {
    return 1 + lcs(X, Y, m - 1, n - 1);
  }
  // Last elements differ
  else {
    return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
  }
}

// Let's test
int main()
{
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, X.size(), Y.size());

  return 0;
}
cpp

Re­kur­sii­vi­sen lä­hes­ty­mis­ta­van op­ti­moin­ti muis­ti­toi­min­non avulla

Kun tar­kas­tel­laan uudelleen re­kur­sii­vis­ta lä­hes­ty­mis­ta­paa, voidaan nähdä, että pääl­lek­käi­set osat lasketaan. Nämä omi­nai­suu­det, joita kutsutaan ”pääl­lek­käi­sik­si osaproblee­mik­si”, tunnetaan Fibonacci-jonoista. Tässäkin ta­pauk­ses­sa re­kur­sii­vi­sia jonoja lasketaan jat­ku­vas­ti ratkaisun löy­tä­mi­sek­si. Prosessin te­hos­ta­mi­sek­si kannattaa käyttää muistia. Toisin sanoen, jo lasketut osaproblee­mit voidaan tallentaa vä­li­muis­tiin kak­siu­lot­tei­ses­sa mat­rii­sis­sa.

Python

def lcs(X, Y, m, n, table):
  
  # Base case
  if (m == 0 or n == 0):
    return 0
  # Already computed value at given position
  if (table[m][n] != -1):
    return table[m][n]
  # Last elements are equal
  if X[m - 1] == Y[n - 1]:
    table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table)
  # Last elements differ
  else:
    table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table))
  return table[m][n]

# Let's test
X = "DAVID"
Y = "DANIEL"
m, n = len(X), len(Y)
# Initialize table fields to `-1`
table = [[-1 for i in range(n + 1)] for j in range(m + 1)]
// Compute and output length of LCS
print(f"Length of LCS is: {lcs(X, Y, m, n, table)}")
python

Java

import java.io.*;

class LCS {

  public static int lcs(String X, String Y, int m, int n, int[][] table) {
    // Base case
    if (m == 0 || n == 0) {
      return 0;
    }
    // Already computed value at given position
    if (table[m][n] != -1) {
      return table[m][n];
    }
    // Last elements are equal
    if(X.charAt(m - 1) == Y.charAt(n - 1)) {
      table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
      return table[m][n];
    }
    // Last elements differ
    else {
      table[m][n] = Math.max(lcs(X, Y, m, n - 1, table),lcs(X, Y, m - 1, n, table));
      return table[m][n];
    }
  }

  // Let's test
  public static void main(String args[]){

    // Initialize variables
    String X = "DAVID";
    String Y = "DANIEL";
    int m = X.length();
    int n = Y.length();
    int[][] table = new int[m + 1][n + 1];
    
    // Initialize table fields to `-1`
    for(int i=0; i < m + 1; i++) {
      for(int j=0; j < n + 1; j++) {
        table[i][j] = -1;
      }
    }

    // Compute and output length of LCS
    int lcsLength = lcs(X, Y, m, n, table);
    System.out.println("Length of LCS is: " + lcsLength);
  }
}
java

C++

#include <bits/stdc++.h>
using namespace std;

int lcs(char *X, char* Y, int m, int n, vector<vector<int>>& table)
{
  // Base case
  if (m == 0 || n == 0)
    return 0;
  // Already computed value at given position
  if (table[m][n] != -1) {
    return table[m][n];
  }
  // Last elements are equal
  if (X[m - 1] == Y[n - 1]) {
    table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
    return table[m][n];
  }
  // Last elements differ
  else { 
    table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
    return table;
  }
}

// Let's test
int main()
{
  // Initialize variables
  char X[] = "DAVID";
  char Y[] = "DANIEL";
  int m = strlen(X);
  int n = strlen(Y);

  // Initialize table with `-1`
  vector<vector<int>> table(m + 1, vector<int>(n + 1, -1));
  
  // Compute and output length of LCS
  cout << "Length of LCS is: " << lcs(X, Y, m, n, table);

  return 0;
}
cpp

Dy­naa­mi­nen oh­jel­moin­ti pi­sim­mäl­le yh­tei­sel­le ali­jo­nol­le

Dy­naa­mi­nen oh­jel­moin­ti on ei-re­kur­sii­vi­nen tapa ratkaista op­ti­moin­tion­gel­mia jakamalla ne pie­nem­piin osion­gel­miin ja rat­kai­se­mal­la ne sitten “alhaalta ylöspäin”. Dy­naa­mis­ta oh­jel­moin­tia so­vel­le­taan muun muassa rei­ti­net­sin­tä­al­go­rit­mien rat­kai­su­na. Pisin yhteinen alijono -ongelma voidaan myös ratkaista dy­naa­mi­sel­la oh­jel­moin­nil­la, kun käytetään kak­siu­lot­teis­ta matriisia.

Python

def lcs(X , Y, m, n): 
  
  # Initialize dynamic programming table fields to `None`
  table = [[None] * (n + 1) for _ in range(m + 1)]
  
  # Compute table values
  for i in range(m + 1):
    for j in range(n + 1):
      # Base case
      if i == 0 or j == 0 :
        table[i][j] = 0
      # Last elements are equal
      elif X[i - 1] == Y[j - 1]:
        table[i][j] = table[i - 1][j - 1]+ 1
      # Last elements differ
      else:
        table[i][j] = max(table[i - 1][j] , table[i][j - 1])
  
  return table[m][n]

# Let's test
X = "DAVID"
Y = "DANIEL"

# Compute and output length of LCS
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")
python

Java

import java.io.*;

class LCS {

  public static int lcs(String X, String Y, int m, int n)
  {
    // Initialize dynamic programming table fields
    int table[][] = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        // Base case
        if (i == 0 || j == 0)
          table[i][j] = 0;
        // Last elements are equal
        else if (X.charAt(i - 1) == Y.charAt(j - 1))
          table[i][j] = table[i - 1][j - 1] + 1;
        // Last elements differ
        else
          table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
      }
    }
    return table[m][n];
  }

  // Let's test
  public static void main(String args[]){

    // Initialize variables
    String X = "DAVID";
    String Y = "DANIEL";
    int m = X.length();
    int n = Y.length();

    // Compute and output length of LCS
    int lcsLength = lcs(X, Y, m, n);
    System.out.println("Length of LCS is: " + lcsLength);
  }
}
java

C++

#include <bits/stdc++.h>
using namespace std;

int lcs(string X, string Y, int m, int n) {
	// Initialize dynamic programming table
	int table[m + 1][n + 1];

	// Compute table values
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			// Base case
			if (i == 0 || j == 0)
				table[i][j] = 0;
			// Last elements are equal
			else if (X[i - 1] == Y[j - 1])
				table[i][j] = table[i - 1][j - 1] + 1;
			// Last elements differ
			else
				table[i][j] = max(table[i - 1][j], table[i][j - 1]);
		}
	}

	return table[m][n];
}

// Let's test
int main() {
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  int m = X.size();
  int n = Y.size();

  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, m, n);

  return 0;
}
cpp
Siirry pää­va­lik­koon