Aritalab:Lecture/Programming/Java/Alignment - Revision history

Adm at 05:46, 20 December 2011

2011-12-20T05:46:21Z

Adm at 05:42, 20 December 2011

2011-12-20T05:42:39Z

Adm: /* クラスおよびペナルティの定義 */

2011-12-20T05:41:25Z

‎クラスおよびペナルティの定義

Adm: /* トレースバック関数 */

2011-12-20T05:40:31Z

‎トレースバック関数

Adm: /* メイン関数 */

2011-12-20T05:39:57Z

‎メイン関数

Adm: /* アルゴリズム */

2011-12-20T05:39:32Z

‎アルゴリズム

Adm: /* トレースバック関数 */

2011-12-20T05:38:02Z

‎トレースバック関数

Adm: moved Aritalab:Lecture/Bioinformatics/Alignment/Java to Aritalab:Lecture/Programming/Java/Alignment

2011-12-15T05:32:44Z

moved Aritalab:Lecture/Bioinformatics/Alignment/Java to Aritalab:Lecture/Programming/Java/Alignment

Adm at 00:46, 15 December 2011

2011-12-15T00:46:18Z

Show changes

Adm: Created page with "配列アライメントアルゴリズムの全体を以下に示します。このページにあるコードを全てつなげて Alignment.java としてコンパイル、実..."

2011-12-14T22:56:56Z

Created page with "配列アライメントアルゴリズムの全体を以下に示します。このページにあるコードを全てつなげて Alignment.java としてコンパイル、実..."

New page

配列アライメントアルゴリズムの全体を以下に示します。このページにあるコードを全てつなげて Alignment.java としてコンパイル、実行してください。
__FORCETOC__
===クラスおよびペナルティの定義===
<pre>
public class Alignment {
private int LOCAL = 0, GLOBAL = 1;
private int AlignType = -1;
private int MatchScore = 1;
private int GapPenalty = -2;
private int MismatchPenalty = -1;
private int[][] scoreTable;
private String seqX, seqY;

public Alignment(String x, String y) {
seqX = x;
seqY = y;
scoreTable = new int[x.length() + 1][y.length() + 1];
}

private void initializeTable() {
scoreTable[0][0] = 0;
for (int i = 1; i < scoreTable.length; i++)
scoreTable[i][0] = scoreTable[i - 1][0] + AlignType * GapPenalty;
for (int i = 1; i < scoreTable[0].length; i++)
scoreTable[0][i] = scoreTable[0][i - 1] + AlignType * GapPenalty;
}

private int getMax(int x, int y, int z, int w) {
int t = x > y ? x : y;
int s = z > w ? z : w;
return (t > s ? t : s);
}

private int getMax(int x, int y, int z) {
int t = x > y ? x : y;
return (t > z ? t : z);
}
</pre>
===トレースバック関数===
重要なのは do { ... } while 文の中身だけで、後はトレースを印刷するための準備です。
<pre>
private String[] traceBack() {
int x = 0, y = 0;
if (AlignType == LOCAL) {
// Search for the maximum score brute-force (very inefficient).
// The max score can be recorded when computing scoreTable.
int max = 0;
for (int i = 0; i < scoreTable.length; i++) {
for (int j = 0; j < scoreTable[0].length; j++)
if (scoreTable[i][j] >= max) {
x = i;
y = j;
max = scoreTable[i][j];
}
}
} else if (AlignType == GLOBAL) {
x = scoreTable.length - 1;
y = scoreTable[0].length - 1;
}
StringBuffer line1 = new StringBuffer();
StringBuffer line2 = new StringBuffer();
line1.append(':');
line1.append(x);
line2.append(':');
line2.append(y);
do {
if (scoreTable[x - 1][y] + GapPenalty == scoreTable[x][y]) {
line1.insert(0, seqX.charAt(x-- - 1));
line2.insert(0, '-');
} else if (scoreTable[x][y - 1] + GapPenalty == scoreTable[x][y]) {
line1.insert(0, '-');
line2.insert(0, seqY.charAt(y-- - 1));
} else {
line1.insert(0, seqX.charAt(x-- - 1));
line2.insert(0, seqY.charAt(y-- - 1));
}
} while (x != 0 && y != 0
&& (AlignType == GLOBAL ? true : scoreTable[x][y] != 0));
line1.insert(0, ':');
line1.insert(0, String.format("%1$3d", x + 1));
line2.insert(0, ':');
line2.insert(0, String.format("%1$3d", y + 1));
return new String[] { line1.toString(), line2.toString() };
}

public void printTable() {
if (scoreTable == null)
return;
StringBuffer sb = new StringBuffer();
for (int i = 0; i < scoreTable.length; i++) {
for (int j = 0; j < scoreTable[0].length; j++)
sb.append(String.format("%1$4d", scoreTable[i][j]));
sb.append("\n");
}
System.out.println(sb.toString());
}

public void printTrace() {
String[] trace = traceBack();
String x = trace[0];
String y = trace[1];
StringBuffer sb = new StringBuffer();
sb.append(" ");
for (int i = 4; x.charAt(i) != ':'; i++)
sb.append(x.charAt(i) == y.charAt(i) ? "|" : " ");
sb.append(" ");
String z = sb.toString();

int width = 50;
int i = -1;
while (++i * width < x.length()) {
System.out.println(x.substring(i * width,
Math.min(x.length(), (i + 1) * width)));
System.out.println(z.substring(i * width,
Math.min(z.length(), (i + 1) * width)));
System.out.println(y.substring(i * width,
Math.min(y.length(), (i + 1) * width)));
}
}
</pre>

===アルゴリズム===
大域アライメントと局所アライメントの違いは、漸化式の候補に 0 があるかないかの違いだけである点に注意しましょう。
<pre>
public void NeedlemanWunsch() {
AlignType = GLOBAL;
initializeTable();
for (int i = 1; i < scoreTable.length; i++)
for (int j = 1; j < scoreTable[0].length; j++)
scoreTable[i][j] = getMax(
scoreTable[i - 1][j] + GapPenalty,
scoreTable[i][j - 1] + GapPenalty,
scoreTable[i - 1][j - 1]
+ (seqX.charAt(i - 1) == seqY.charAt(j - 1) ? MatchScore
: MismatchPenalty));
}

public void SmithWaterman() {
AlignType = LOCAL;
initializeTable();
for (int i = 1; i < scoreTable.length; i++)
for (int j = 1; j < scoreTable[0].length; j++)
scoreTable[i][j] = getMax(0,
scoreTable[i - 1][j] + GapPenalty,
scoreTable[i][j - 1] + GapPenalty,
scoreTable[i - 1][j - 1]
+ (seqX.charAt(i - 1) == seqY.charAt(j - 1) ? MatchScore
: MismatchPenalty));
}
</pre>
===メイン関数===
<pre>
public static void main(String[] args) {
Alignment A = new Alignment("aattgaaggattgctcggataatcgcc","gctaggatcacggccatggcaagcgcg");
//Alignment A = new Alignment("aattgaagg","gctagg");
//A.NeedlemanWunsch();
A.SmithWaterman();
A.printTable();
A.printTrace();
}
}
</pre>

← Older revision		Revision as of 05:42, 20 December 2011
Line 1:		Line 1:
−	配列アライメントアルゴリズムの全体を以下に示します。このページにあるコード部分を全てつなげて Alignment.java ~~としてコンパイル、実行してください。このファイルだけで動きます。~~	+	配列アライメントアルゴリズムの全体を以下に示します。このページにあるコード部分を全てつなげて Alignment.java としてコンパイル、実行してください。ただし、インクリメントを表す＋＋は半角に直してください。（なぜか半角で＋＋と書くと、wiki ページ上で表示されなくなってしまいます。）
		+
		+	＋＋の修正さえして貰えれば、このファイルだけで動きます。
		+
	__FORCETOC__		__FORCETOC__

@@ Line 1: / Line 1: @@
-配列アライメントアルゴリズムの全体を以下に示します。このページにあるコード部分を全てつなげて Alignment.java としてコンパイル、実行してください。ただし、インクリメントを表す＋＋は半角に直してください。（なぜか 半角で＋＋と書くと、wiki ページ上で表示されなくなってしまいます。）
+配列アライメントアルゴリズムの全体を以下に示します。このページにあるコード部分を全てつなげて Alignment.java としてコンパイル、実行してください。
-＋＋の修正さえして貰えれば、このファイルだけで動きます。
+このファイルだけで動きます。
 __FORCETOC__
@@ Line 24: / Line 24: @@
    private void initializeTable() {
      scoreTable[0][0] = 0;
-     for (int i = 1; i < scoreTable.length; i＋＋)
+     for (int i = 1; i < scoreTable.length; i&#43;&#43;)
        scoreTable[i][0] = scoreTable[i - 1][0] + AlignType * GapPenalty;
-     for (int i = 1; i < scoreTable[0].length; i＋＋)
+     for (int i = 1; i < scoreTable[0].length; i&#43;&#43;)
        scoreTable[0][i] = scoreTable[0][i - 1] + AlignType * GapPenalty;
+   }
@@ Line 51: / Line 51: @@
        // The max score can be recorded when computing scoreTable.
        int max = 0;
-       for (int i = 0; i < scoreTable.length; i＋＋) {
+       for (int i = 0; i < scoreTable.length; i&#43;&#43;) {
-         for (int j = 0; j < scoreTable[0].length; j＋＋)
+         for (int j = 0; j < scoreTable[0].length; j&#43;&#43;)
            if (scoreTable[i][j] >= max) {
              x = i;
@@ Line 95: / Line 95: @@
      StringBuffer sb = new StringBuffer();
      sb.append("    ");
-     for (int i = 4; x.charAt(i) != ':'; i＋＋)
+     for (int i = 4; x.charAt(i) != ':'; i&#43;&#43;)
        sb.append(x.charAt(i) == y.charAt(i) ? "|" : " ");
      sb.append("    ");
@@ Line 102: / Line 102: @@
      int width = 50;
      int i = -1;
-     while (＋＋i * width < x.length()) {
+     while (&#43;&#43;i * width < x.length()) {
        System.out.println(x.substring(i * width,
            Math.min(x.length(), (i + 1) * width)));
@@ Line 119: / Line 119: @@
      AlignType = GLOBAL;
      initializeTable();
-     for (int i = 1; i < scoreTable.length; i＋＋)
+     for (int i = 1; i < scoreTable.length; i&#43;&#43;)
-       for (int j = 1; j < scoreTable[0].length; j＋＋)
+       for (int j = 1; j < scoreTable[0].length; j&#43;&#43;)
          scoreTable[i][j] = getMax(
              scoreTable[i - 1][j] + GapPenalty,
@@ Line 132: / Line 132: @@
      AlignType = LOCAL;
      initializeTable();
-     for (int i = 1; i < scoreTable.length; i＋＋)
+     for (int i = 1; i < scoreTable.length; i&#43;&#43;)
-       for (int j = 1; j < scoreTable[0].length; j＋＋)
+       for (int j = 1; j < scoreTable[0].length; j&#43;&#43;)
          scoreTable[i][j] = getMax(
 ,
@@ Line 150: / Line 150: @@
        return;
      StringBuffer sb = new StringBuffer();
-     for (int i = 0; i < scoreTable.length; i＋＋) {
+     for (int i = 0; i < scoreTable.length; i&#43;&#43;) {
-       for (int j = 0; j < scoreTable[0].length; j＋＋)
+       for (int j = 0; j < scoreTable[0].length; j&#43;&#43;)
          sb.append(String.format("%1$4d", scoreTable[i][j]));
        sb.append("\n");