http://rosalind.info/problems/as-graph/
http://en.wikipedia.org/wiki/Bioinformatics

字符串处理、正则表达式

s = gets
print [s.count('A'), s.count('C'), s.count('G'), s.count('T')] * ' '

print gets.gsub('T','U')

s = gets
s.gsub!('A','a'); s.gsub!('T','A'); s.gsub!('a','T')
s.gsub!('C','c'); s.gsub!('G','C'); s.gsub!('c','G')
print s.reverse

$buf = gets()

def gc(s)
	gcc = 0.0
	s.each_char{|si|		
		gcc += 1 if (si == 'G' || si == 'C') 
	}
	return gcc / s.size
end

def getdna()
	dna = gets().chomp
	dna += $buf.chomp while ($buf = gets()) && ($buf[0] != '>')	
	return dna
end

dna = "$"

while $buf do
	_id, _dna = $buf[1..-1], getdna()		
	id, dna = _id, _dna if gc(_dna) > gc(dna)
end

puts id
print gc(dna) * 100, '%'

s = gets.chomp; t = gets.chomp; dist = 0
0.upto(s.size-1){|i|
	dist += 1 if s[i] != t[i]		
}
p dist

s = gets.chomp; n = s.length; a = Array.new(n){Hash.new(0)}

begin	
	0.upto(n-1){|i|
		a[i][s[i]] += 1
	}
end while s = gets


def scan(a, n, ch)
	print ch,':'
	0.upto(n-1){|i|
		print ' ', a[i][ch]
	}
	puts
end


def common(ai)
	return 'A' if (ai['A'] >= ai['C'] && ai['A'] >= ai['G'] && ai['A'] >= ai['T']) 	
	return 'C' if (ai['C'] >= ai['A'] && ai['C'] >= ai['G'] && ai['C'] >= ai['T']) 
	return 'G' if (ai['G'] >= ai['A'] && ai['G'] >= ai['C'] && ai['G'] >= ai['T']) 
	return 'T'
end

a.each{|ai|
	#ai.sort_by{|key, value| value}
	#print ai.begin().value
	print common(ai)
}	
puts

		
scan(a, n, 'A'); scan(a, n, 'C'); scan(a, n, 'G'); scan(a, n, 'T')

/* .................................................................................................................................. */

const int N = 1009;

pair<string, string> A[N];
int n;

bool adj(string a, string b, int k){
    if (a == b) return false;
    REP(i, k) if (a[SZ(a)-k+i] != b[i]) return false;
    return true;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    string id, dna; cin >> id; while (id[0] == '>'){
        ERS(id, 0), A[n].fi = id, CLR(dna);
        while (cin >> id && id[0] != '>') dna += id;
        A[n++].se = dna;
    }

    REP_2(i, j, n, n) if (adj(A[i].se, A[j].se, 3)){
        cout << A[i].fi << " " << A[j].fi << endl;
    }
}

dict = {
    'UCA' => 'S',    # Serine
    'UCC' => 'S',    # Serine
    'UCG' => 'S',    # Serine
    'UCU' => 'S',    # Serine
    'UUC' => 'F',    # Phenylalanine
    'UUU' => 'F',    # Phenylalanine
    'UUA' => 'L',    # Leucine
    'UUG' => 'L',    # Leucine
    'UAC' => 'Y',    # Uyrosine
    'UAU' => 'Y',    # Uyrosine
    'UAA' => '_',    # Stop
    'UAG' => '_',    # Stop
    'UGC' => 'C',    # Cysteine
    'UGU' => 'C',    # Cysteine
    'UGA' => '_',    # Stop
    'UGG' => 'W',    # Uryptophan
    'CUA' => 'L',    # Leucine
    'CUC' => 'L',    # Leucine
    'CUG' => 'L',    # Leucine
    'CUU' => 'L',    # Leucine
    'CCA' => 'P',    # Proline
    'CCC' => 'P',    # Proline
    'CCG' => 'P',    # Proline
    'CCU' => 'P',    # Proline
    'CAC' => 'H',    # Histidine
    'CAU' => 'H',    # Histidine
    'CAA' => 'Q',    # Glutamine
    'CAG' => 'Q',    # Glutamine
    'CGA' => 'R',    # Arginine
    'CGC' => 'R',    # Arginine
    'CGG' => 'R',    # Arginine
    'CGU' => 'R',    # Arginine
    'AUA' => 'I',    # Isoleucine
    'AUC' => 'I',    # Isoleucine
    'AUU' => 'I',    # Isoleucine
    'AUG' => 'M',    # Methionine
    'ACA' => 'T',    # Uhreonine
    'ACC' => 'T',    # Uhreonine
    'ACG' => 'T',    # Uhreonine
    'ACU' => 'T',    # Uhreonine
    'AAC' => 'N',    # Asparagine
    'AAU' => 'N',    # Asparagine
    'AAA' => 'K',    # Lysine
    'AAG' => 'K',    # Lysine
    'AGC' => 'S',    # Serine
    'AGU' => 'S',    # Serine
    'AGA' => 'R',    # Arginine
    'AGG' => 'R',    # Arginine
    'GUA' => 'V',    # Valine
    'GUC' => 'V',    # Valine
    'GUG' => 'V',    # Valine
    'GUU' => 'V',    # Valine
    'GCA' => 'A',    # Alanine
    'GCC' => 'A',    # Alanine
    'GCG' => 'A',    # Alanine
    'GCU' => 'A',    # Alanine
    'GAC' => 'D',    # Aspartic Acid
    'GAU' => 'D',    # Aspartic Acid
    'GAA' => 'E',    # Glutamic Acid
    'GAG' => 'E',    # Glutamic Acid
    'GGA' => 'G',    # Glycine
    'GGC' => 'G',    # Glycine
    'GGG' => 'G',    # Glycine
    'GGU' => 'G'    # Glycine    
};

mRNA = gets.chomp
puts mRNA.gsub(/\w{3}/).each(&dict.method(:[]))[0..-1].gsub(/_.*/, '')

。。。mRNA、蛋白质（Protein）、氨基酸（Amino Acid）、密码子（Genetic Code）。。。

dict = {
    'TCA' => 'S',    # Serine
    'TCC' => 'S',    # Serine
    'TCG' => 'S',    # Serine
    'TCT' => 'S',    # Serine
    'TTC' => 'F',    # Phenylalanine
    'TTT' => 'F',    # Phenylalanine
    'TTA' => 'L',    # Leucine
    'TTG' => 'L',    # Leucine
    'TAC' => 'Y',    # Tyrosine
    'TAT' => 'Y',    # Tyrosine
    'TAA' => '_',    # Stop
    'TAG' => '_',    # Stop
    'TGC' => 'C',    # Cysteine
    'TGT' => 'C',    # Cysteine
    'TGA' => '_',    # Stop
    'TGG' => 'W',    # Tryptophan
    'CTA' => 'L',    # Leucine
    'CTC' => 'L',    # Leucine
    'CTG' => 'L',    # Leucine
    'CTT' => 'L',    # Leucine
    'CCA' => 'P',    # Proline
    'CCC' => 'P',    # Proline
    'CCG' => 'P',    # Proline
    'CCT' => 'P',    # Proline
    'CAC' => 'H',    # Histidine
    'CAT' => 'H',    # Histidine
    'CAA' => 'Q',    # Glutamine
    'CAG' => 'Q',    # Glutamine
    'CGA' => 'R',    # Arginine
    'CGC' => 'R',    # Arginine
    'CGG' => 'R',    # Arginine
    'CGT' => 'R',    # Arginine
    'ATA' => 'I',    # Isoleucine
    'ATC' => 'I',    # Isoleucine
    'ATT' => 'I',    # Isoleucine
    'ATG' => 'M',    # Methionine
    'ACA' => 'T',    # Threonine
    'ACC' => 'T',    # Threonine
    'ACG' => 'T',    # Threonine
    'ACT' => 'T',    # Threonine
    'AAC' => 'N',    # Asparagine
    'AAT' => 'N',    # Asparagine
    'AAA' => 'K',    # Lysine
    'AAG' => 'K',    # Lysine
    'AGC' => 'S',    # Serine
    'AGT' => 'S',    # Serine
    'AGA' => 'R',    # Arginine
    'AGG' => 'R',    # Arginine
    'GTA' => 'V',    # Valine
    'GTC' => 'V',    # Valine
    'GTG' => 'V',    # Valine
    'GTT' => 'V',    # Valine
    'GCA' => 'A',    # Alanine
    'GCC' => 'A',    # Alanine
    'GCG' => 'A',    # Alanine
    'GCT' => 'A',    # Alanine
    'GAC' => 'D',    # Aspartic Acid
    'GAT' => 'D',    # Aspartic Acid
    'GAA' => 'E',    # Glutamic Acid
    'GAG' => 'E',    # Glutamic Acid
    'GGA' => 'G',    # Glycine
    'GGC' => 'G',    # Glycine
    'GGG' => 'G',    # Glycine
    'GGT' => 'G'    # Glycine   
};

dna = gets.chomp

while exon = gets do
	dna.gsub!(exon.chomp, '')
end

puts dna.gsub(/\w{3}/).each(&dict.method(:[]))[0..-1].gsub(/_.*/, '')

外显子（Exon）、内含子（Intron）

s = gets.chomp; n = s.length

def cp(a, b)
	return a == 'G' && b == 'C' || a == 'C' && b == 'G' || a == 'A' && b == 'T' || a == 'T' && b == 'A'
end

def test(s)	
	n = s.length
	0.upto(n/2){|i|
		return false if !cp(s[i], s[n-1-i])
	}
	return true
end

4.upto(8){|len|	
	next if len.odd?	
	0.upto(n-len){|l|
		r = l + len - 1
		print l+1, ' ', len, "\n" if (test(s[l..r]))
	}
}

概率

I =->{gets.split.map &:to_f}
I[].each{|ai|	
	p (ai**2 + (1-ai)**2) / 2
}

I =->{gets.split.map &:to_f}
m, n = I[]

I[].each{|ai|  	
    p (n - m + 1) * ((ai**2 + (1-ai)**2) / 2) ** m
}

字符串匹配

T = gets().chomp
P = gets().chomp

Tn, Pn = T.length, P.length

Pi = []; Pi[0] = j = -1

0.upto(Pn-1){|i|
	j = Pi[j] while (j >= 0 && P[i] != P[j])
	i += 1; j += 1; Pi[i] = P[i] == P[j] ? Pi[j] : j	
}

j = 0

0.upto(Tn-1){|i|
	j = Pi[j] while (j >= 0 && T[i] != P[j])
	i += 1; j += 1; p i-Pn+1 if j == Pn
}

P = gets().chomp + '$'
Pn = P.length


Pi = []; Pi[0], Pi[1], i, j = -1, 0, 2, 0

while (i < Pn) do
	if (P[i-1] == P[j]) then
		j +=1; Pi[i] = j; i += 1
	else
		if (j > 0) then 
			j = Pi[j]
		else 
			Pi[i] = 0; i += 1
		end
	end
end

puts Pi[1..-1]*' '

s = gets.chomp
t = gets.chomp

i = 0; t.each_char{|ti|
	i += 1 while s[i] != ti; i += 1;
	p i
}

/* .................................................................................................................................. */

const int N = 1009;

string S[N]; int dp[N][N];
int n;

void check(string s){
    FOR(i, 1, n) if (S[i].find(s) == string::npos) return;
    OT(s), exit(0);
}


int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    string s; while (cin >> s){
        S[n++] = s;
    }

    FOR(i, 1, n) if (SZ(S[i]) < SZ(S[0])) swap(S[0], S[i]);

    int n0 = SZ(S[0]); DWN(len, n0-1, 0){
        REP(i, n0-len){
            s = S[0].substr(i, len);
            check(s);
        }
    }
}

生成排列、组合

/* .................................................................................................................................. */

const int N = 10;
int A[N];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;

    printf("%d\n", f); DO(f){
        REP_1(i, n) OT(A[i]);
        next_permutation(A + 1, A + n + 1);
        puts("");
    }
}

/* .................................................................................................................................. */

const int N = 10;
int A[N];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int n, f = 1; REP_1_C(i, RD(n)) A[i] = i, f *= i;
    printf("%d\n", f*_1(n)); DO(f){
        REP(s, _1(n)){
            REP_1(j, n){
                if (!_1(s, (n-j))) putchar('-');
                OT(A[j]);
            }
            puts("");
        }
        next_permutation(A + 1, A + n + 1);
    }
}

/* .................................................................................................................................. */

const int N = 10;
char S[N]; int A[N];
int n; LL k;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    char str[100]; gets(str);
    REP_C(i, strlen(str)) if (str[i] != ' ') S[n++] = str[i];
    RD(k); DO(pow(n, k)){
        DWN(i, k, 0) putchar(S[A[i]]); puts("");
        A[0]++; for (int i=0;A[i]==n;A[i]=0,++A[++i]);
    }
}

/* .................................................................................................................................. */

const int N = 15;

char C[N]; int A[N];
int n, k;

void dfs(int dep = 0){
    if (dep){
        REP(i, dep) putchar(i[A][C]);
        puts("");
    }

    if (dep == k) return;
    REP(i, n) A[dep]=i, dfs(dep+1);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    char str[109]; REP_C(i, strlen(gets(str))) if (str[i] != ' ')
        C[n++] = str[i];
    RD(k);

    dfs();
}

搜索

/* .................................................................................................................................. */

const int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
const int N = 10, L = 3628800;
int n = 10;

int D[L]; int a[N], st, ed; bool c[N];

int encode(){ // Cantor
    int x = 0; REP(i, n){
        int t = 0; FOR(j, i+1, n)
            if (a[i]>a[j]) ++t;
        x = x * (n-i) + t;
    }
    return x;
}

void decode(int x){
    RST(a, c); REP(i, n){
        while (i[a][c]) ++a[i];
        while (x >= F[n-i-1]){
            x -= F[n-i-1]; ++a[i];
            while (i[a][c]) ++a[i];
        }
        i[a][c] = true;
    }
}

void rev(int l, int r){
    REP(i, (r - l + 1) / 2)
        swap(a[l+i], a[r-i]);
}

int Q[L], cz, op; int bfs(){
    if (st == ed) return 0;
    Q[cz = 0] = st, op = 1;
    RST(D); D[st] = 1;
    while (cz < op){
        int u = Q[cz++]; decode(u);
        FOR(len, 1, n){
            REP(l, n - len){
                int r = l + len; rev(l, r); int v = encode(); rev(l, r);
                if (D[v]) continue;
                if (v == ed) return D[u];
                Q[op++] = v;
                D[v] = D[u] + 1;
            }
        }
    }
    return -1;
}


int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &a[0])){
        FOR(i, 1, n) --RD(a[i]); st = encode();
        REP(i, n) --RD(a[i]); ed = encode();
        OT(bfs());
    }
}

/* .................................................................................................................................. */

template<class T1, class T2> ostream& operator <<(ostream& cout, const pair<T1, T2> &rhs){
    cout << rhs.fi+1 << " " << rhs.se+1;
    return cout;
}

const int F[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
const int N = 10, L = 3628800;
int n = 10;

int D[L], pre[L]; PII opt[L]; int a[N], st, ed; bool c[N];

int encode(){ // Cantor
    int x = 0; REP(i, n){
        int t = 0; FOR(j, i+1, n)
            if (a[i]>a[j]) ++t;
        x = x * (n-i) + t;
    }
    return x;
}

void decode(int x){
    RST(a, c); REP(i, n){
        while (i[a][c]) ++a[i];
        while (x >= F[n-i-1]){
            x -= F[n-i-1]; ++a[i];
            while (i[a][c]) ++a[i];
        }
        i[a][c] = true;
    }
}

void rev(int l, int r){
    REP(i, (r - l + 1) / 2)
        swap(a[l+i], a[r-i]);
}

void print_path(int v){
    if (v == st) return;
    print_path(pre[v]);
    cout << opt[v] << endl;
}

int Q[L], cz, op; void bfs(){
    if (st == ed) {puts(0); return;}
    Q[cz = 0] = st, op = 1;
    RST(D); D[st] = 1;
    while (cz < op){
        int u = Q[cz++]; decode(u);
        FOR(len, 1, n){
            REP(l, n - len){
                int r = l + len; rev(l, r); int v = encode(); rev(l, r);
                if (D[v]) continue; opt[v] = MP(l, r), pre[v] = u;
                if (v == ed){OT(D[u]), print_path(v); return;}
                Q[op++] = v, D[v] = D[u] + 1;
            }
        }
    }
}


int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &a[0])){
        FOR(i, 1, n) --RD(a[i]); st = encode();
        REP(i, n) --RD(a[i]); ed = encode();
        bfs();
    }
}

动态规划

/* .................................................................................................................................. */

const int N = 1009;

char A[N], B[N];
int dp[N][N], n, m;

void print_path(int i, int j){
    if (!i || !j) return;
    if (A[i] == B[j] && dp[i][j] == dp[i-1][j-1] + 1){
        print_path(i-1, j-1), putchar(A[i]);
    }
    else if (dp[i-1][j] > dp[i][j-1]){
        print_path(i-1, j);
    }
    else{
        print_path(i, j-1);
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    RS(A+1), RS(B+1), n = strlen(A+1), m = strlen(B+1);

    REP_2_1(i, j, n, m){
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        if (A[i] == B[j]) checkMax(dp[i][j], dp[i-1][j-1] + 1);
    }

    print_path(n, m);
}

s = gets.chomp; n = s.length; s = '$' + s
t = gets.chomp; m = t.length; t = '$' + t

dp = Array.new(n+1){Array.new(m+1){0}}

def min(a, b)
	return a < b ? a : b
end

1.upto(n){|i|
	dp[0][i] = dp[i][0] = i
}

1.upto(n){|i|
	1.upto(m){|j|		
		dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))
	}
}

p dp[n][m]

s = gets.chomp; n = s.length; s = '$' + s
t = gets.chomp; m = t.length; t = '$' + t

dp = Array.new(n+1){Array.new(m+1){0}}

def min(a, b)
	return a < b ? a : b
end

1.upto(n){|i|
	dp[0][i] = dp[i][0] = i
}

1.upto(n){|i|
	1.upto(m){|j|		
		dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]) + 1, dp[i-1][j-1] + (s[i] != t[j] ? 1 : 0))
	}
}

# build alignment .. .
s_ = t_ = ''; i, j = n, m
while !i.zero? || !j.zero? do	
	if (j.zero? || dp[i][j] == dp[i-1][j] + 1) then
		s_ += s[i]; t_ += '-'
		i -= 1
	elsif (i.zero? || dp[i][j] == dp[i][j-1] + 1) then
		s_ += '-'; t_ += t[j]
		j -= 1
	else		
		s_ += s[i]; t_ += t[j]		
		i -= 1; j -= 1
	end
end

s_.reverse!; t_.reverse!
puts dp[n][m], s_, t_

Posted by xiaodao
Category: 日常