基因组重组排序算法综述

随着快速测序技术的发展,对大规模DNA分子的研究与其中的基因相对次序有关。基因组重组是计算生物学的一个重要研究领域,是基因组在基因水平比较分析的基础。其研究目标是找最短的重组操作序列,将一种基因组转变为另一种基因组。基于分子生物学的实验证明,这种序列有助于估计不同基因组间的进化事件。基因组进化过程虽然非常复杂,但可用3种基本的重组操作模拟,即反转（reversal）、移位（transloeation）和转位（transposition）。本文讨论了这些操作相关的重组算法以及各种排序距离的计算方法。     

有向基因组移位排序算法的比较与评测

基因组重组是生物进化的一种重要模式.虽然其生物过程非常复杂,但可归结为三种基本操作:移位、反转和转位.移位排序问题要求计算从一个基因组转化为另一个基因组所需的最少移位次数以及相应的移位序列.对于有向基因组移位排序问题,目前有三个多项式时间算法.已有算法在分析偶隔离带时漏掉一种情况,从而导致对某些特殊实例的计算结果是不正确的.通过给出这种特殊情况下找有效移位的方法,用Java语言将三个算法实现为移位排序软件-SG-BT,其计算效率优于现有的移位排序软件CTRD.通过随机产生的实验数据对三个算法的计算性能进行了测试,结果表明,三个算法的计算效率在基因数为0-70000时基本相同,在基因数为80000-100000时才表现出差异,并且随着基因数的增加差异越发明显.通过进一步实验,分析了产生上述结果的原因.最后,用SGBT对人和老鼠的部分基因进行排序并给出排序结果.     

基因组一般移位排序问题的多项式时间算法

基因组移位排序在基因组重组排序计算研究中占有重要位置.交互型移位和非交互型移位均为移位的特殊形式.目前见到的多种移位排序算法均是针对交互型移位而得到的,未见基因组一般移位排序计算的研究结果.文中讨论包括交互型移位和非交互型移位的一般移位排序问题的求解方法,给出该问题的一个多项式时间算法.算法的关键在于将一般移位排序问题在线性时间内归约为交互型移位排序问题,利用交互型移位排序的算法来求解一般移位排序.作者的算法证实了Ozery-Flato等关于一般移位排序问题可以多项式时间解决的猜测.     

计算生物学中有关基因组翻转距离的NPC问题

1 基因组翻转距离问题的提出 20世纪80年代末,Jeffrey Palmer及其同事在对比甘蓝与芜箐甘蓝的基因序列时发现,排列形成两种基因序列的分子几乎完全相同,只是这些分子在两种基因中的排列顺序不一样。这一发现以及其后的研究表明,基因重组是生物演化过程中的一个基本特征。基因重组研究中多次遇到要用尽可能少的次数将一条基因序列中的片断翻转连接成新的基因的问题,这就是后来由D.Sankoff等提出的基因组翻转距离问题,或抽象为有向符号序列的翻转距离问题,D.Sankoff等猜测该问题是NP难解问题,然而他们没能给出证明。     

面向排序学习的特征分析的研究

排序是信息检索中一个重要的环节,当今已经提出百余种用于构建排序函数的特征,如何利用这些特征构建更有效的排序函数成为当今的一个热点问题,因此排序学习（Learning to Rank）,一个信息检索与机器学习的交叉学科,越来越受到人们的重视。从排序特征的构建方式易知,特征之间并不是完全独立的,然而现有的排序学习方法的研究,很少在特征分析的基础上,从特征重组与选择的角度,来构建更有效的排序函数。针对这一问题,提出如下的模型框架：对构建排序函数的特征集合进行分析,然后重组与选择,利用排序学习方法学习排序函数。基于这一框架,提出四种特征处理的算法：基于主成分分析的特征重组方法、基于MAP、前向选择和排序学习算法隐含的特征选择。实验结果显示,经过特征处理后,利用排序学习算法构建的排序函数,一般优于原始的排序函数。     

k支配能力排序轮廓查询算法

随着轮廓查询应用的扩展,轮廓查询被扩展为其他更复杂的查询问题,包括k支配轮廓、reverse轮廓、k最多支配轮廓等等.然而,现存的轮廓查询不符合某些用户需求,还需要研究新的轮廓查询及其相关算法.为了满足用户需求,提出k支配能力轮廓的概念,同时提出一种快速的k支配能力排序轮廓查询算法(KRA).由于不确定性数据带有概率,KRA算法不能直接应用于不确定性数据.针对不确定性轮廓查询的特点,提出不确定性k支配能力轮廓的概念,并提出不确定性k支配能力排序轮廓查询算法(KRA_U).实验结果表明,算法KRA和KRA_U均可以高效地计算出k支配能力轮廓.     

有向基因组移位排序问题的O(n2)快速算法

有向基因组移位排序问题在计算生物学研究中占有重要位置．以前最好的算法时间复杂度为O(n^2logn)．该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O(n^2)．算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O(n)，总时间复杂度由此降为O(n^2)．     

通过交互式移位-插入-删除进行基因组排序的较快算法

多染色体基因组进化问题中常见的重组事件就是移位(translocation),对此已有很多研究成果.但事实上更为普遍的情况是2个基因组包含不同基因,这需要考虑插入和删除事件.对于"通过移位-插入-删除进行基因组排序(简称SG-TID)"这个问题,此前已有一个求解移位-删除(或者移位-插入)序列的近似算法,以及求解SG-TID问题的启发式算法.在给出了移位-插入-删除距离的表达公式后,给出了在增加O(n)存储空间的条件下,O(n2)时间内求解该问题的精确算法.该算法比此前给出的算法要快.     

排序合并Join算法的新结果

Join操作是数据库中最昂贵和最常用的操作.排序合并Join算法是实现Join操作的重要算法,得到了普遍接受并广为应用.在重新研究了排序合并Join算法后发现,同时对两个Join关系进行外排序是不必要的,会带来很大的额外开销.针对这个问题,提出了一种基于单关系外排序的分治Join算法,并在该算法的基础上提出了基于单关系外排序的并行分治Join算法.理论和实验结果证明,基于单关系排序的分治Join算法高于排序合并Join算法.特别是在并行计算环境下,基于单关系排序的并行分治Join算法的效率远远高于排序合并     

转移、消“零”、返回排序法

排序是计算机在处理信息过程中的一种重要操作,而内部排序又是排序的一个重要组成部分。以往人们在处理排序问题时,大多基于对关键字的比较和交换这两种操作的排序算法,因而能达到的最佳排序时间为O(N㏒_2N),其中N为数据个数。至目前为止,以上述算法为基础的各种排序方法中,QUICK SORT的方案具有最佳的平均性能。本文提出一种转移、消“零”、返回的新排序方法(以下简称转移法)。