多重アラインメント | Codetter（こーどったー）

import java.util.ArrayList;

public class MultipleAlignment {
    
    public static final double MATCH   =  2.0;
    public static final double UNMATCH = -1.0;
    public static final double GAP     = -1.0;
    
    /*
       グローバルアラインメントで用いるテーブルを生成
    */
    Node[][] similarityTable(Profile p1, Profile p2){
        Node[][] t = new Node[p1.length()+1][p2.length()+1];
        
        for(int i = 0; i < p1.length()+1; i++){
            for(int j = 0; j < p2.length()+1; j++){
                t[i][j] = new Node();
                if(i == 0 || j == 0) continue;
                
                double s = p1.matchScoreAt(i-1, j-1, p2);
                t[i][j].m = t[i-1][j-1].m + s;
                if(t[i][j].m < t[i-1][j].m + GAP){
                    t[i][j].m = t[i-1][j].m + GAP;
                    t[i][j].d = 1;
                }
                if(t[i][j].m < t[i][j-1].m + GAP){
                    t[i][j].m = t[i][j-1].m + GAP;
                    t[i][j].d = 2;
                }
            }
        }
        return t;
    }
    
    /*
       グローバルアラインメントによるスコア
    */
    double similarityScore(Profile p1, Profile p2){
        return similarityTable(p1, p2)[p1.length()][p2.length()].m;
    }
    
    /*
       2つのProfileに対するグローバルアラインメント
    */
    Profile globalAlignment(Profile p1, Profile p2){
        Node[][] t = similarityTable(p1, p2);
        
        int i = p1.length(), j = p2.length();
        while(i != 0 || j != 0){
            if(j == 0 || t[i][j].d == 1){
                p2.insert(j, '_');
                i--;
            }else if(i == 0 || t[i][j].d == 2){
                p1.insert(i, '_');
                j--;
            }else{
                i--;
                j--;
            }
        }
        
        p1.add(p2);
        return p1;
    }
    
    /*
       累進法による多重アラインメント
    */
    Profile progressiveMethod(String[] s){
        
        // 与えられた配列1つ1つを元にProfileを生成
        Profile[] p = new Profile[s.length];
        for(int i = 0; i < s.length; i++){
            p[i] = new Profile();
            p[i].add(s[i]);
        }
        
        // Profileの類似度を、値が大きい順にリストへ格納
        ArrayList<SimScore> list = new ArrayList<SimScore>();
        for(int i = 1; i < s.length; i++){
            for(int j = 0; j < i; j++){
                SimScore sim = new SimScore(i, j, similarityScore(p[i], p[j]));
                int k = 0;
                while(k < list.size() && sim.score < list.get(k).score) k++;
                list.add(k, sim);
            }
        }
        
        // リストの先頭から順番にデータを取り出し、Profileを合成
        int last = 0;
        while(list.size() > 0){
            SimScore sim = list.remove(0);
            if(sim.x != sim.y){
                last = sim.x;
                p[sim.x] = globalAlignment(p[sim.x], p[sim.y]);
                for(int i = 0; i < list.size(); i++){
                    SimScore sim2 = list.get(i);
                    if(sim2.x == sim.y) sim2.x = sim.x;
                    if(sim2.y == sim.y) sim2.y = sim.x;
                }
            }
        }
        return p[last];
    }
    
    public static void main(String[] args){
        MultipleAlignment m = new MultipleAlignment();
        String[] s = {"AGATGTGATTG", "AGCGTGTGCT", "GACGTAGACT", "AGATTCGAT"};
        Profile p = m.progressiveMethod(s);
        for(int i = 0; i < p.size(); i++){
            System.out.println(p.getString(i));
        }
    }
    
    // テーブル内の一要素を表すクラス
    class Node {
        double m; // スコア
        int d;    // ポインタ
    }
    
    /*
       Profile同士の類似度を保持するクラス
       累進法では、より似ているProfileを優先して合成するので、
       その順序づけに用いる。
    */
    class SimScore {
        int x, y;
        double score;
        SimScore(int x, int y, double score){
            this.x = x;
            this.y = y;
            this.score = score;
        }
    }
}

// 複数の配列の合成を表すクラス
class Profile {
    
    ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();
    
    void add(String s){
        list.add(new StringBuilder(s));
    }
    
    void add(Profile p){
        for(int i = 0; i < p.size(); i++){
            list.add(p.getStringBuilder(i));
        }
    }
    
    int size(){
        return list.size();
    }
    
    int length(){
        return list.get(0).length();
    }
    
    double matchScoreAt(int index1, int index2, Profile p){
        double sum = 0.0;
        for(int i = 0; i < list.size(); i++){
            StringBuilder sb = list.get(i);
            sum += p.matchScoreAt(index2, sb.charAt(index1));
        }
        return sum / list.size();
    }
    
    double matchScoreAt(int index, char c){
        double sum = 0.0;
        for(int i = 0; i < list.size(); i++){
            StringBuilder sb = list.get(i);
            sum += (sb.charAt(index) == c) ? MultipleAlignment.MATCH : MultipleAlignment.UNMATCH;
        }
        return sum / list.size();
    }
    
    void insert(int index, char c){
        for(int i = 0; i < list.size(); i++){
            list.get(i).insert(index, c);
        }
    }
    
    StringBuilder getStringBuilder(int index){
        return list.get(index);
    }
    
    String getString(int index){
        return list.get(index).toString();
    }
}