计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2010年
11期
2011-2023
,共13页
郝凡昌%栾峻峰%朱大铭%张鹏%李明
郝凡昌%欒峻峰%硃大銘%張鵬%李明
학범창%란준봉%주대명%장붕%리명
基因重组%交互式移位%插入%删除%距离公式%算法
基因重組%交互式移位%插入%刪除%距離公式%算法
기인중조%교호식이위%삽입%산제%거리공식%산법
多染色体基因组进化问题中常见的重组事件就是移位(translocation),对此已有很多研究成果.但事实上更为普遍的情况是2个基因组包含不同基因,这需要考虑插入和删除事件.对于"通过移位-插入-删除进行基因组排序(简称SG-TID)"这个问题,此前已有一个求解移位-删除(或者移位-插入)序列的近似算法,以及求解SG-TID问题的启发式算法.在给出了移位-插入-删除距离的表达公式后,给出了在增加O(n)存储空间的条件下,O(n2)时间内求解该问题的精确算法.该算法比此前给出的算法要快.
多染色體基因組進化問題中常見的重組事件就是移位(translocation),對此已有很多研究成果.但事實上更為普遍的情況是2箇基因組包含不同基因,這需要攷慮插入和刪除事件.對于"通過移位-插入-刪除進行基因組排序(簡稱SG-TID)"這箇問題,此前已有一箇求解移位-刪除(或者移位-插入)序列的近似算法,以及求解SG-TID問題的啟髮式算法.在給齣瞭移位-插入-刪除距離的錶達公式後,給齣瞭在增加O(n)存儲空間的條件下,O(n2)時間內求解該問題的精確算法.該算法比此前給齣的算法要快.
다염색체기인조진화문제중상견적중조사건취시이위(translocation),대차이유흔다연구성과.단사실상경위보편적정황시2개기인조포함불동기인,저수요고필삽입화산제사건.대우"통과이위-삽입-산제진행기인조배서(간칭SG-TID)"저개문제,차전이유일개구해이위-산제(혹자이위-삽입)서렬적근사산법,이급구해SG-TID문제적계발식산법.재급출료이위-삽입-산제거리적표체공식후,급출료재증가O(n)존저공간적조건하,O(n2)시간내구해해문제적정학산법.해산법비차전급출적산법요쾌.
