您当前所在位置: 首页 > 学者

朱大铭

  • 17浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 73下载

  • 0评论

  • 引用

期刊论文

An O(n2) algorithm for signed translocation

朱大铭Lusheng Wang a Daming Zhu b Xiaowen Liu b Shaohan Ma b

Journal of Computer and System Sciences 70(2005)284-299,-0001,():

URL:

摘要/描述

Genome rearrangement is an important area in computational biology. There are three basic operations, reversal, translocation and transposition. Herewestudy the translocation operations. Multi-chromosomal genomes frequently evolve by translocation events that exchange genetic material between two chromosomes.We focus on the signed case, where the direction of each gene is known. The signed translocation problem asks to find the minimum number of translocation operations as well as the sequence of translocation operations to transform one genome into the other.A linear-time algorithm that computes the minimum number of translocation operations was given in a linear-time algorithm for computing translocation distance between signed genomes [16]. However, that algorithm cannot give the optimum sequence of translocation operations. The best known algorithm that can give the optimum sequence of translocation operations for signed translocation problem runs in O(n2 log n) time. In this paper, we design an O(n2) algorithm.

【免责声明】以下全部内容由[朱大铭]上传于[2006年12月01日 02时12分48秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。

我要评论

全部评论 0

本学者其他成果

    同领域成果