1、計(jì)算生物學(xué)是現(xiàn)今世界的熱門學(xué)科,計(jì)算生物學(xué)研究的有關(guān)成果直接影響著人類在生物進(jìn)化、基因制藥等領(lǐng)域的研究進(jìn)展.生物學(xué)、化學(xué)、數(shù)學(xué)、計(jì)算機(jī)科學(xué)等各領(lǐng)域?qū)＜覍W(xué)者都在關(guān)注著計(jì)算生物學(xué)的發(fā)展.基因重組對于計(jì)算機(jī)科學(xué)理論研究來說,其基本課題是基因組距離的計(jì)算問題,以及基于基因組距離計(jì)算的進(jìn)化樹問題.基因組距離主要為基因序列之間的Reversal距離(R_距離、翻轉(zhuǎn)距離)和基因組之間的Translocation距離(T_距離).目前,基于基因組距離計(jì)

2、算的各種進(jìn)化樹問題是理論研究的熱點(diǎn)與難點(diǎn)<'[20-26]>.Reversal和Translocation均是十分復(fù)雜的生物進(jìn)化過程,Sankoff將這些過程歸結(jié)為簡單的基因組重組模型,提出Reversal排序和Translocation排序問題,并統(tǒng)稱為基因組重組排序問題<'[18,19]>.該文就與基因組重組排序有關(guān)的距離計(jì)算問題進(jìn)行研究,得到三個(gè)主要結(jié)果:(1)證明基于基因組Reversal距離的星樹問題是NP難解的,證明該問題不