计算分子生物学中的最优共同祖先序列题解

问题描述

我们需要在给定的完全二叉树结构中，找到所有叶子节点序列的最优共同祖先序列。这个共同祖先序列需要满足从根节点到所有叶子节点的边代价总和最小，其中边代价定义为两个相连节点序列在对应位置上不同氨基酸的数量。

解题思路

1. 树结构处理：将输入的叶子节点序列组织成完全二叉树结构
2. 位置独立处理：对序列的每个位置独立处理，因为不同位置的选择互不影响
3. 位掩码技术：使用位掩码表示每个位置上可能的氨基酸选择
4. 贪心选择：自底向上计算每个内部节点的最优氨基酸选择，优先选择所有子节点共有的氨基酸，否则选择任意一个子节点的氨基酸并增加代价

标程

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char seq[1024][1024]; // 存储输入的叶子节点序列
int T[2048]; // 用于构建树的数组
int n, m; // n:序列数量，m:序列长度

int main() {
    while(scanf("%d%d", &n, &m), n+m) { // 读取输入直到n=l=0
        // 读取所有叶子节点序列
        for(int i = 0; i < n; i++)
            scanf("%s", seq[i]);

        int cost = 0; // 总代价初始化为0
        
        // 对序列的每个位置独立处理
        for(int p = 0; p < m; p++) {
            // 初始化叶子节点：用位掩码表示氨基酸
            for(int x = 0; x < n; x++)
                T[x+n] = 1<<(seq[x][p]-'A');
            
            // 自底向上构建树
            for(int rt = n-1; rt >= 1; rt--) {
                int lch = rt<<1; // 左子节点索引
                int rch = rt<<1|1; // 右子节点索引
                
                // 尝试找子节点共有的氨基酸
                T[rt] = T[lch] & T[rch];
                
                // 如果没有共有氨基酸，则合并子节点的可能氨基酸并增加代价
                if(T[rt] == 0) {
                    T[rt] = T[lch] | T[rch];
                    cost++;
                }
            }
            
            // 从根节点的位掩码中提取最优氨基酸
            char ch = 'A';
            while((T[1] & 1) == 0) {
                ch++;
                T[1] >>= 1;
            }
            printf("%c", ch); // 输出该位置的最优氨基酸
        }
        
        printf(" %d\n", cost); // 输出总代价
    }
    return 0;
}

关键点解析

1. 位掩码表示：

   • 每个氨基酸用1位表示（A=1<<0, B=1<<1,...）
   • 叶子节点存储对应位置氨基酸的位掩码
   • 内部节点存储子节点可能的氨基酸组合

2. 自底向上构建：

   • 从叶子节点开始向上计算
   • 优先选择子节点共有的氨基酸（位与操作）
   • 若无共有氨基酸，则合并子节点的可能氨基酸（位或操作）并增加代价

3. 最优氨基酸选择：

   • 从根节点的位掩码中选择最低位的氨基酸（ASCII码最小的）
   • 这样确保在多种可能选择时有一致的输出

4. 复杂度分析：

   • 时间复杂度：O(m×n)，对每个位置处理所有节点
   • 空间复杂度：O(n×m)，存储所有序列和树结构

示例分析

对于输入：

4 3
AAG
AAA
GGA
AGA

处理过程：

1. 第一位置：A(1), A(1), G(64), A(1) → 根节点选择A，代价1
2. 第二位置：A(1), A(1), G(64), G(64) → 根节点选择G，代价1
3. 第三位置：G(64), A(1), A(1), A(1) → 根节点选择A，代价1

最终输出：AGA 3

该算法高效地解决了在完全二叉树中寻找最优共同祖先序列的问题，通过位运算和贪心策略确保了最优解的计算。