郝凡昌 栾峻峰 朱大铭 张 鹏 李 明. 通过交互式移位-插入-删除进行基因组排序的较快算法[J]. 计算机研究与发展, 2010, 47(11): 2011-2023.
 引用本文: 郝凡昌 栾峻峰 朱大铭 张 鹏 李 明. 通过交互式移位-插入-删除进行基因组排序的较快算法[J]. 计算机研究与发展, 2010, 47(11): 2011-2023.
Hao Fanchang, Luan Junfeng, Zhu Daming, Zhang Peng, and Li Ming. A Faster Algorithm for Sorting Genomes by Reciprocal Translocation, Insertion and Deletion[J]. Journal of Computer Research and Development, 2010, 47(11): 2011-2023.
 Citation: Hao Fanchang, Luan Junfeng, Zhu Daming, Zhang Peng, and Li Ming. A Faster Algorithm for Sorting Genomes by Reciprocal Translocation, Insertion and Deletion[J]. Journal of Computer Research and Development, 2010, 47(11): 2011-2023.

## A Faster Algorithm for Sorting Genomes by Reciprocal Translocation, Insertion and Deletion

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

Abstract: The genome sorting problem considers how species are related to each other by computing rearrangement distances between their genomes. The rearrangement distance between two genomes is the minimum number of genetic mutations needed to transform one to another. Multi-chromosomal genomes evolve frequently by a rearrangement event called translocation, which have been well studied. Many research works have been done for the case where only translocations occur. However, the more common conditions in computational biology is that there are genes that appear only in the source or target genome. A method solving this involves the evolution events called insertion and deletion. There has been an approximation algorithm for sorting genomes using translation, insertion and deletion (SG-TID). In this paper, we analyze the relationship between the three operations and then define the invertibility among the operations, through which SG-TID is transformed to a simpler one called sorting genomes by translocation and deletions (SG-TD). Additionally in the algorithm solving the SG-TD problem, we use O(n) memory space to record some important parameters, which help reduce the time complexity to a considerable level. We first give formulas for computing the rearrangement distance for SG-TID, then present a simpler algorithm to compute the rearrangement distance and find the corresponding transformation sequence in O(n) space and O(n\+2) time, which is faster and more practical than the previous TID algorithm.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈