計(jì)算生物學(xué)中有關(guān)基因組距離問(wèn)題研究.pdf

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

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