遺伝子配列類似性問題CCR版(KMモードマッチング)
2798 ワード
【問題15】遺伝子配列類似性問題(dna.cpp/c/pas)
師範大学附中陳超鋭
メモリ制限256 MB時間制限1 s
【テーマ背景】
最長共通サブシーケンス問題は生物情報学におけるシーケンス対問題の特例である.このような問題は分子生物学とモード識別に広く応用されている.その中で最も主要な応用は遺伝子配列の類似性を測定することである.進化分子生物学の研究では,ある重要なDNA配列断片が異なる種によく現れることが分かった.遺伝子配列の類似性を測定する際に,特定のDNA配列断片を特に閉じる必要がある場合は,サブストリング含有制約を有する最長共通サブ配列問題を考察する.
【課題の説明】この問題は、2つの長さがそれぞれmおよびnであるDNA配列XおよびYと、長さがpであるパターンのサブ列P.が、サブ配列を含む制約を有する最長共通サブ配列を有する問題として、xおよびYが、そのサブ列であるPを含まない最長共通サブ配列を見つけることである.例えば、与えられたDNA配列xおよびYがそれぞれX=AATGCCTAGGCである場合、Y=CGATCTGGAC、モードサブシーケンスP=TGGCの場合、サブシーケンスATCTGGCは、Pがそのサブ列である最長共通サブシーケンスを含まない、XおよびYの制約のない最長共通サブシーケンスであり、ATCTGC(一意ではないかもしれない)である.プログラミングタスク:所与のシーケンスXとYがサブストリングP制約を含まない最長の共通サブシーケンスを見つける.
【入力形式】(dna.in)
ファイルの1行目には正の整数m,n,pが与えられ、所与のシーケンスX,Yおよびモードサブ列Pの長さをそれぞれ表す.m<200,n<200,p<200.次の3行は、シーケンスXおよびYおよびパターンサブストリングPをそれぞれ与える.
【出力フォーマット】(dna.out)
計算されたXおよびYは、サブストリングP制約を含まない最長共通サブシーケンスの長さ出力を有し、存在しない場合は長さ0である.
【サンプル入力】
11 10 4
AATGCCTAGGC
CGATCTGGAC
TGGC
【サンプル出力】
6
【データ範囲】
20%のデータ:060%のデータに対して0100%のデータ:01年以上KMPを書いていないのでいろいろ怪我ができませんが...
preの意味をかすかに覚えているだけで(1-iの後半を1-pre[i]に合わせる)
やっとstdのスケジュールが分かったんだけどどうしたんだろうWA
なぜならkは最内層で循環しなければならないから......(考えてみればf[i][j]k]更新のf[i+1][j+1][t]、tはkの前にある可能性がある)
f[i][j][k]は、aがiにマッチングし、bがjにマッチングしたとき、最後の数ビットがパターン列pにマッチングし、最後の数ビットがk番目のビットにマッチングしたときの最大マッチング長を自然に表す
師範大学附中陳超鋭
メモリ制限256 MB時間制限1 s
【テーマ背景】
最長共通サブシーケンス問題は生物情報学におけるシーケンス対問題の特例である.このような問題は分子生物学とモード識別に広く応用されている.その中で最も主要な応用は遺伝子配列の類似性を測定することである.進化分子生物学の研究では,ある重要なDNA配列断片が異なる種によく現れることが分かった.遺伝子配列の類似性を測定する際に,特定のDNA配列断片を特に閉じる必要がある場合は,サブストリング含有制約を有する最長共通サブ配列問題を考察する.
【課題の説明】この問題は、2つの長さがそれぞれmおよびnであるDNA配列XおよびYと、長さがpであるパターンのサブ列P.が、サブ配列を含む制約を有する最長共通サブ配列を有する問題として、xおよびYが、そのサブ列であるPを含まない最長共通サブ配列を見つけることである.例えば、与えられたDNA配列xおよびYがそれぞれX=AATGCCTAGGCである場合、Y=CGATCTGGAC、モードサブシーケンスP=TGGCの場合、サブシーケンスATCTGGCは、Pがそのサブ列である最長共通サブシーケンスを含まない、XおよびYの制約のない最長共通サブシーケンスであり、ATCTGC(一意ではないかもしれない)である.プログラミングタスク:所与のシーケンスXとYがサブストリングP制約を含まない最長の共通サブシーケンスを見つける.
【入力形式】(dna.in)
ファイルの1行目には正の整数m,n,pが与えられ、所与のシーケンスX,Yおよびモードサブ列Pの長さをそれぞれ表す.m<200,n<200,p<200.次の3行は、シーケンスXおよびYおよびパターンサブストリングPをそれぞれ与える.
【出力フォーマット】(dna.out)
計算されたXおよびYは、サブストリングP制約を含まない最長共通サブシーケンスの長さ出力を有し、存在しない場合は長さ0である.
【サンプル入力】
11 10 4
AATGCCTAGGC
CGATCTGGAC
TGGC
【サンプル出力】
6
【データ範囲】
20%のデータ:0
preの意味をかすかに覚えているだけで(1-iの後半を1-pre[i]に合わせる)
やっとstdのスケジュールが分かったんだけどどうしたんだろうWA
なぜならkは最内層で循環しなければならないから......(考えてみればf[i][j]k]更新のf[i+1][j+1][t]、tはkの前にある可能性がある)
f[i][j][k]は、aがiにマッチングし、bがjにマッチングしたとき、最後の数ビットがパターン列pにマッチングし、最後の数ビットがk番目のビットにマッチングしたときの最大マッチング長を自然に表す
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<functional>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<=n;i++)
#define MAXN (200+10)
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int f[MAXN][MAXN][MAXN];
int pre[MAXN];
void kmp()
{
pre[0]=-1,pre[1]=0;
int j=0;
Fork(i,2,p+1)
{
if(j^-1&&c[i]^c[j+1]) j=pre[j];
pre[i]=++j;
}
}
int main()
{
freopen("dna.in","r",stdin);
freopen("dna.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
scanf("%s%s%s",a+1,b+1,c+1);
kmp();
memset(f,128,sizeof(f));
f[0][0][0]=0;
Fork(i,0,n)
Fork(j,0,m)
Fork(k,0,p-1)
{
if (!f[i][j][k]&&k) continue;
if (i<n) f[i+1][j][k]=max(f[i+1][j][k],f[i][j][k]);
if (j<m) f[i][j+1][k]=max(f[i][j+1][k],f[i][j][k]);
if (i<n&&j<m&&a[i+1]==b[j+1])
{
int t=k;
while (t^-1&&c[t+1]^a[i+1]) t=pre[t];
++t;
f[i+1][j+1][t]=max(f[i+1][j+1][t],f[i][j][k]+1);
}
}
int ans=0;
Rep(i,p-1) ans=max(ans,f[n][m][i]);
cout<<ans<<endl;
return 0;
}