信息散度和Alignment空間的一些研究.pdf

1、隨著信息科學(xué)的不斷發(fā)展，人們對信息論學(xué)科的認(rèn)識日益加深，信息論學(xué)科與其他學(xué)科的交叉滲透也越來越廣。目前對信息論的研究已經(jīng)從香農(nóng)當(dāng)年僅限于通信系統(tǒng)的數(shù)學(xué)理論的狹義范圍擴(kuò)展開來，像智能計(jì)算、生物、金融等領(lǐng)域都開始大量運(yùn)用信息論的有關(guān)知識.在以上這些領(lǐng)域中，涉及到了各種隨機(jī)分布差異的概念，需要利用信息量去衡量它們之間的區(qū)別。另外，在通信科學(xué)與生命科學(xué)中，對差錯的概念已經(jīng)有所推廣，不再僅僅是經(jīng)典的字符改變形成的差錯，而且還擴(kuò)展到了字符的插入與刪

2、除形成的差錯。面對這些新問題，本文從三個部分進(jìn)行了初步的探討。
　　 第一部分：信息散度(Information Divergence)的研究
　　 本文的第二章主要討論了信息散度的問題.信息散度在信息論中又被稱為離散量，主要用來衡量兩個隨機(jī)分布之間的差異.比如最早提出的相對熵(即Kullback-Leibler散度)就是其中最為人所熟知的一種。本章首先介紹了一些著名的信息散度，然后討論了信息散度與概率分布空間中度量的關(guān)

3、系。2003年，Endres和Schindelin在論文"A New Metric for Probability Distributions”中將Jensen-Shannon散度(有的論文也稱為capacitory discrimination)作了改進(jìn)，證明了改進(jìn)后的結(jié)果可以成為概率分布空間中的度量。本章在此論文的基礎(chǔ)之上繼續(xù)研究，從而得到了一類由概率分布生成的新度量v文中證明了得到新度量的充分必要條件，討論了新度量的最值問題.本章

4、最后對Jensen—Shannon散度的凸性作了一點(diǎn)探討。
　　 第二部分: Fq上的Alignment空間的相關(guān)研究以及計(jì)數(shù)問題
　　 在數(shù)據(jù)處理問題中，差錯的類型有多種，除了符號的替換之外還有數(shù)據(jù)的插入與丟失等等情況發(fā)生，本文稱這樣的差錯為廣義差錯或者突變誤差.由廣義差錯可以得到一種非線性空間--Alignment空間，這種空間在編碼、密碼、計(jì)算機(jī)與生物信息等等領(lǐng)域中有著廣泛的應(yīng)用。比如帶插入/刪除的信道編碼、生物序

5、列比對、圖像處理等，都需要用到廣義差錯和Alignment空間中的有關(guān)概念與性質(zhì)。本文在這一部分對廣義差錯和Alignment空間作了詳細(xì)的說明和討論。
　　 本文的第三章介紹了Fq集合上的Alignment空間的相關(guān)概念.首先我們對Fq集合上的Alignment空間和Alignment距離的定義作了說明，然后對Alignment距離的計(jì)算方法作了介紹，這個計(jì)算方法就是經(jīng)典的動態(tài)規(guī)劃算法.接下來文中討論了廣義差錯的Levensh

6、tein距離與Alignment距離的關(guān)系，最后介紹了該空間的一些簡單的性質(zhì)。
　　 第四章主要討論一種研究Alignment空間的途徑--序列的模結(jié)構(gòu)理論以及虛擬符號的運(yùn)算理論。本章首先簡要介紹了序列的模結(jié)構(gòu)理論，然后詳細(xì)介紹了比對序列的虛擬符號運(yùn)算理論，嚴(yán)格證明了兩序列的比對序列間虛擬符號運(yùn)算子的存在性，并且證明了等位運(yùn)算子成為保距運(yùn)算子和微調(diào)運(yùn)算子的充分必要條件。
　　 第五章主要討論Alignment空間中的計(jì)數(shù)

7、問題。Alignment空間中的計(jì)數(shù)問題主要分為兩類，本章開始對其作了說明。然后文中詳細(xì)討論了F2上的n維Alignment子空間中Alignment距離為n與Alignment距離為2的序列對數(shù)目。得到了F2上的n維Alignment子空間中Alignment距離為n的序列有2n對，F(xiàn)2上的n維燦gnment子空間中Alignment距離為2的序列有(2n2-7n+11)-6對的結(jié)果，并且得到了Alinment距離為n的序列對滿足的充

8、分必要條件，說明了它們的最長的最小罰分比對序列就是最短的最大得分比對序列的結(jié)論.
　　 第三部分；由一般拓?fù)涠攘靠臻g生成的Alignment空間
　　 在第二部分討論的基礎(chǔ)之上，Alignment空間還可以繼續(xù)擴(kuò)展到更—般的情況，由一般的拓?fù)涠攘靠臻g同樣可以產(chǎn)生Alignment空間.第六章中首先對由一般拓?fù)涠攘靠臻g所產(chǎn)生的Alignment空間和其中的Alignment距離的定義作了說明，然后證明了此時得到的Align