Needleman-Wunsch 算法是生物信息学的基石

public class NeedlemanWunsch {
    private static final int MATCH_SCORE = 2;
    private static final int MISMATCH_PENALTY = -1;
    private static final int GAP_PENALTY = -2;

    public static Alignment align(String seq1, String seq2) {
        int m = seq1.length();
        int n = seq2.length();
        int[][] scoreMatrix = new int[m + 1][n + 1];

        // 初始化第一行和第一列
        for (int i = 0; i <= m; i++) {
            scoreMatrix[i][0] = i * GAP_PENALTY;
        }
        for (int j = 0; j <= n; j++) {
            scoreMatrix[0][j] = j * GAP_PENALTY;
        }

        // 填充得分矩阵
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int match = scoreMatrix[i - 1][j - 1] + 
                           (seq1.charAt(i - 1) == seq2.charAt(j - 1) ? MATCH_SCORE : MISMATCH_PENALTY);
                int delete = scoreMatrix[i - 1][j] + GAP_PENALTY;
                int insert = scoreMatrix[i][j - 1] + GAP_PENALTY;
                scoreMatrix[i][j] = Math.max(Math.max(match, delete), insert);
            }
        }

        // 回溯生成比对结果
        StringBuilder alignedSeq1 = new StringBuilder();
        StringBuilder alignedSeq2 = new StringBuilder();
        int i = m, j = n;

        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && 
                scoreMatrix[i][j] == scoreMatrix[i - 1][j - 1] + 
                (seq1.charAt(i - 1) == seq2.charAt(j - 1) ? MATCH_SCORE : MISMATCH_PENALTY)) {
                // 对角移动：匹配/不匹配
                alignedSeq1.append(seq1.charAt(i - 1));
                alignedSeq2.append(seq2.charAt(j - 1));
                i--;
                j--;
            } else if (i > 0 && scoreMatrix[i][j] == scoreMatrix[i - 1][j] + GAP_PENALTY) {
                // 向上移动：序列2插入空位
                alignedSeq1.append(seq1.charAt(i - 1));
                alignedSeq2.append('-');
                i--;
            } else {
                // 向左移动：序列1插入空位
                alignedSeq1.append('-');
                alignedSeq2.append(seq2.charAt(j - 1));
                j--;
            }
        }

        // 反转结果（因为是从后往前构建的）
        String aligned1 = alignedSeq1.reverse().toString();
        String aligned2 = alignedSeq2.reverse().toString();
        int score = scoreMatrix[m][n];

        return new Alignment(aligned1, aligned2, score);
    }

    public static class Alignment {
        private String seq1;
        private String seq2;
        private int score;

        public Alignment(String seq1, String seq2, int score) {
            this.seq1 = seq1;
            this.seq2 = seq2;
            this.score = score;
        }

        public String getSeq1() {
            return seq1;
        }

        public String getSeq2() {
            return seq2;
        }

        public int getScore() {
            return score;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("序列1: ").append(seq1).append("\n");
            sb.append("序列2: ").append(seq2).append("\n");
            sb.append("比对得分: ").append(score).append("\n");
            
            // 生成比对标记行
            StringBuilder matchLine = new StringBuilder();
            for (int i = 0; i < seq1.length(); i++) {
                if (seq1.charAt(i) == seq2.charAt(i)) {
                    matchLine.append('|');
                } else if (seq1.charAt(i) == '-' || seq2.charAt(i) == '-') {
                    matchLine.append(' ');
                } else {
                    matchLine.append(':');
                }
            }
            sb.append("比对标记: ").append(matchLine).append("\n");
            
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        String seq1 = "AGTACGCA";
        String seq2 = "TATGC";
        
        Alignment alignment = align(seq1, seq2);
        System.out.println(alignment);
    }
}