基因组数据分析是计算机科学的热点，生物信息学的核心。决策安全是算法理论研究的热点，社会选择学的核心。选择基因组数据分析及决策控制的典型计算需求，提炼组合优化问题模型，设计问题的求解算法，证明问题的计算复杂性。是基因组数据分析和决策安全组合问题求解方法的新进展，在植物育种和医学疾病诊断、医药设计、社会选择安全控制等研究与实践中具有具有广泛应用前景。

(1)片段填充，是基因组序列组装的一个基本阶段。为填充那些基因组序列片段框架的空隙，以基因组比较作为手段，以基因组的公共邻接数目最大化为目标，建立了基因组片段填充组合问题模型。证明了问题的计算复杂性，并设计出该问题的常数近似算法。将基因组双面片段填充的近似性能比改进到1.4+ε。代表性论文1，2被他人引用14次。

(2)无向基因组重组排序，是追踪基因组演化历史，推断生命亲缘关系的典型组合问题模型。其中移位是基因组的一种基本重组变异模式。无向基因组移位排序，是一个被研究20余年的生物信息学和计算机科学领域颇有代表性的组合问题。设计出该问题的近似性能比为1.5的多项式时间近似算法。之后分别将该问题的近似性能比改进到1.4和1.375。在无向基因组移位排序近似算法设计研究中，给出无向断点图2-圈分解的多项式精确算法，解决了一个无向基因组重组排序算法设计中一个典型的开放问题。短块移动是特殊的基因组重组操作。设计出基因组短块移动排序的近似性能比为14/11的多项式时间近似算法，并给出该问题特殊版本的一个1+ε近似多项式时间近似算法。还将一般基因组短块移动排序的近似性能比改进到5/4。代表性论文3，4被他人引用25次。

(3)基因组的公共子串划分，是通过基因组大数据压缩，实现降低基因组比较分析复杂度的重要手段。最小公共子串划分旨在将两个基因组划分成完成相同的子序列片段集合，以公共子序列数目达到最小为目标。证明即使两个基因组都是二元时，该问题的计算复杂性。设计了解答该问题的第一个参数算法。蛋白质结合位点预测，一直是医药设计面临的关键计算需求。给出利用枚举蛋白质局部结构寻找最稳定蛋白质结合位点的方法，该方法有效提高了蛋白质结合位点预测的准确度(论文5，6；他引29次)。

(4)通过投票确定胜出者是计算社会选择的一个基本决策模型。投票系统控制算法是投票系统安全的重要基础。研究了Plurality、Condorcet、Approval和Maximin胜出机制下，投票系统控制问题的参数化计算复杂性，证明以增加或减少投票人或候选人为手段，使特定候选人中选或落选为目标的控制行为，不存在固定参数可解算法。证明最大最小选举控制问题的参数复杂性，首次设计出该问题的参数算法。代表性论文7，8被他人引用75次。

1. 下载详细PDF版/Doc版

提示：为方便大家复制编辑，博主已将PDF文件制作为Word/Doc格式文件。