GRAPPA算法描述.docVIP

GRAPPA算法描述 GRAPPA算法基本思想： 假设基因序列： g1, g2, ? ? ?, gn 每个都标注正负方向，如gi或-gi 在基因突变过程中，会产生转座、倒位、插入、删除等情况。 gi与gj之间的倒位让原序列变为： 基因gi,gi+1,… ,gj 转座到gk让原序列变为 对于基因组G1和G2，我们定义距离 G1, G2 为从G1到G2所需的最小变化步数。 GRAPPA算法描述： 1.确定各region的基因目录。 基因目录的确定可以缩小研究范围并且提高全局精确度。 由于不清楚基因的顺序，目录确定过程中顺序的决定基于猜测。这种猜测是基于以下：改变基因顺序的进化事件较为稀有；两个子系同时发生变化的可能性要小于其母系发生变化。 因此，对于每个内部节点，当两个子系的局部基因目录已知，就会面临三种可能性（对于母系基因的决定）： 1．如果两个子系在同一个region具有基因g，则其母系在同region具有基因g。 2．如果两个子系均没有g，则母系也没有g。 3．g出现在两个子系的不同region，则母系的任一个region都不会有g。 2.种系发生研究以及祖先基因组的重构 在现有的基因目录基础上，进行种系发生的重构。 通过第一步，将基因目录简化处理后，就可以通过GRAPPA来推断突变的系统发生学内容。 测试所有可能的树，（枚举）找到其中拥有最少倒位的。对于每个树，设定了一个下限，来决定树是否值得进行打分操作。最低分的树被用作系统发生树。 GRAPPA算法起源于Sankoff and Blanchette 1998 的BP分析。为了确定最优重构树，这个程序将所给门类中所有可能的拓扑树打分（以树的边长总数为准），并且取得分最小的树。这是一个NP完全问题，因为他要求计算内部基因组节点。在算法中，初始内部节点以某种方式集合，然后生成树向着降低总边界长度的方向，不断反向替代基因组节点，直至整棵树不再变化。早期GRAPPA算法只能计算长度相同序列（无法处理删除、插入、倒位）。这个限制后来被Jijun Tang et al（Scaling up accurate phylogenetic reconstruction）所解决。 Moret et al. 2001 优化了此算法，Caprara 2001 和 SiepelMoret 2001 解决了断点和倒位的问题。Moret et al. 2002b 的研究显示了倒位中间值比断点中间值更有效，所以优化后的GRAPPA算法用了这个中间值。 在以前的研究中，许多算法，如贪心法、最小生成树法等，都被用来计算最小变化步数，其指导思想未有太大出入，只是算法优化程度有所差异，这里就不一一展开了。 由于IR的序列特殊性，IR中基因突变的会造成GRAPPA算法误差 GRAPPA算法的改进： 将基因组中IR序列抽出，将反向部分去除 将抽出后的IR序列合并为一个新序列 以此序列构建进化树 实验步骤 研究过程——目前获得测序的几种蕨类 Adiantum capillus-veneris 铁线蕨 Alsophila spinulosa 木沙椤 Angiopteris evecta 莲座蕨属 Psilotum nudum Pteridium aquilinum subsp Ceratopteris richardii EMBOSS的palindrome有哪些信誉好的足球投注网站