C++ / Shotgun sequencing implementation

/*

 * http://sosal.kr/

 * made by so_Sal

 */

 

 

 

 

출처: http://www.wiley.com/college/boyer/0470003790/cutting_edge/shotgun_seq/shotgun.htm 

 

 

http://sosal.tistory.com/612

Shotgun sequencing 이론에 대한 내용은 위 링크를 참조하세요.

 

예~전에 bioinformatics 경진대회에 참가하면서 구현했던 프로그램이었는데

블로그에 공유해봅니다 ^^

 

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <list>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <sstream>

#include <fstream>

#include <ctime>

#include <windows.h>

 

#define BUFSIZE 1024

 

using namespace std;

 

void mkSPtable(const char* pattern, int *SPtable, int m)

{

 int i, k;  

 

 k=-1;

 SPtable[0]=-1;

 

 for(i=1 ; i<m-1 ; i++)

 {

  while(k>=0 && pattern[k+1]!=pattern[i])

  {

   k=SPtable[k];

  }

 

  if(pattern[k+1]==pattern[i])

  {

   k++;

  }

  SPtable[i]=k;

 }

}

 

int kmp(const char* text, const char* pattern, int n, int m)

{

 int SPtable[BUFSIZE];

 int i, j;

 

 mkSPtable(pattern, SPtable, m);

 

 j=-1;

 

 for(i=0 ; i<=n-1 ; i++)

 {

  while(j>=0 && pattern[j+1]!=text[i])

  {

   j=SPtable[j];

  }

 

  if(pattern[j+1]==text[i])

  {

   j++;

  }

 

  if(j==m-1)

  {

   return 1;

  }

 }

 

 return 0;

}

///////////////////////////KMP 알고리즘을 이용한 string matching

 

int main()

{

srand(time(0));

vector<string> v;

 

ofstream output;

ifstream input;

string in;

output.open("./output.txt");

input.open("./input.txt");

while(! input.eof() ){

input >> in;

v.push_back(in);

}

v.pop_back();

 

int sz=v[0].size();

char tmp1[100];

char tmp2[100];

for(int i=sz ;i>0; i--)

{

for(int Cur=0; Cur<v.size() ; Cur++)

{

for(int j=Cur+1 ; j<v.size() ; j++)

{

if(kmp(v[Cur].substr(0, i).c_str(), v[j].substr(sz-i, i).c_str(), i, i))

{

v[Cur]=v[j].substr(0, sz-i)+v[Cur];

v.erase(v.begin()+j);

output<<i<<": Left comb"<<endl;

Cur--;

break;

}

if(kmp(v[Cur].substr(v[Cur].size()-i, i).c_str(), v[j].substr(0, i).c_str(), i, i))

{

v[Cur]=v[Cur]+v[j].substr(i, v[j].size()-i);

v.erase(v.begin()+j);

output<<i<<" right comb "<<endl;

Cur--;

break;

}

}

}

}

output<<"v.size() :  "<<v.size()<<endl;

output<<"======================"<<endl;

 

output << v[0] << endl;

}  

 

모든 sequence 들 중에 가장 많은 overlapped scope를 가지는 sequence들끼리 겹치는 방식입니다.

코드가 간단해서 자세한 주석없이 이해하실 수 있을거라 생각합니다! (물론 KMP 알고리즘은 아니지만 ^^;)