2019考研计算机：山东大学计算机科学与技术学院科研亮点六

考研网

2019考研复习正在紧张的进行中，为了更好的帮助同学们学习。新东方在线为大家整理了“山东大学计算机科学与技术学院科研亮点：基因组重组”的相关信息，解决各位考生的疑惑，提醒大家要合理安排复习时间，做好复习规划。希望对大家的复习有所帮助!
    基因组的重组距离是推演物种演化历史的重要证据。上世纪九十年代初，加拿大院士David
Sankoff最先将基因组重组抽象为Reversal(翻转)、Translocation(移位)、Tranposition(转位)等三种基本的改变基因相对位置的重组操作，后来又衍生出Block
Move(块移动)、Double cut and Join(DCJ、二次切割并连接)、Cut and
Paste(切割再粘贴)等新的重组操作。自此，如何用指定的重组操作将一个基因组转化为另一个基因组的重组距离问题，成为理论计算机科学及计算生物学研究的经典问题，其算法与计算复杂性被广泛而深入的研究。
    智能算法与软件课题组对此类问题展开深入研究并取得若干重要成果。证明了基因组移位排序重组问题是NP-难的，并先后设计了近似性能比为1.75、1.5+的近似算法，相关结果发表在JCSS(IF
1.106)、IEEE/ACM Trans. Computational Biology and Bioinformatics(IF
1.616)等高期刊杂志上。设计了基因组DCJ排序重组问题的1.5-近似算法，相关结果发表在高水平杂志 Bioinformatics(IF
5.323)上。设计了基因组Cut and Paste重组问题的2.25-近似算法，发表在高水平杂志发表在JCSS(IF 1.106)。