《生物信息學(xué)》PPT課件.ppt

簡(jiǎn)介,生物信息學(xué)（Bioinformatics）是20世紀(jì)80年代末隨著人類基因組計(jì)劃的啟動(dòng)而興起的一門新型交叉學(xué)科，它體現(xiàn)了生物學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)、物理學(xué)等學(xué)科間的滲透與融合。 生物信息學(xué)通過(guò)對(duì)生物學(xué)實(shí)驗(yàn)數(shù)據(jù)的獲取、加工、存儲(chǔ)、檢索與分析，達(dá)到揭示數(shù)據(jù)所蘊(yùn)含的生物學(xué)意義從而解讀生命活動(dòng)規(guī)律的目的。 生物信息學(xué)不僅是一門學(xué)科，更是一種重要的研究開(kāi)發(fā)平臺(tái)與工具，是今后進(jìn)行幾乎所有生命科學(xué)研究的推手。,生物技術(shù)與生物信息學(xué)的區(qū)別及聯(lián)系,生物信息學(xué)的發(fā)展歷史,人類基因組計(jì)劃（HGP）,人類基因組計(jì)劃由美國(guó)科學(xué)家于1985年提出，1990年啟動(dòng)。根據(jù)該計(jì)劃，在2015年要把人體約4萬(wàn)個(gè)基因的密碼全部揭開(kāi)，同時(shí)繪制出人類基因的譜圖，也就是說(shuō)，要揭開(kāi)組成人體4萬(wàn)個(gè)基因的30億個(gè)堿基對(duì)的秘密。HGP與曼哈頓原子彈計(jì)劃和阿波羅計(jì)劃并稱為三大科學(xué)計(jì)劃，被譽(yù)為生命科學(xué)的登月計(jì)劃。,隨著基因組計(jì)劃的不斷發(fā)展，海量的生物學(xué)數(shù)據(jù)必須通過(guò)生物信息學(xué)的手段進(jìn)行收集、分析和整理后，才能成為有用的信息和知識(shí)。換句話說(shuō)，人類基因組計(jì)劃為生物信息學(xué)提供了興盛的契機(jī)。上文所說(shuō)的基因、堿基對(duì)、遺傳密碼子等術(shù)語(yǔ)都是生物信息學(xué)需要著重研究的地方。,數(shù)據(jù)與信息,數(shù)據(jù)是人們?yōu)榱朔从晨陀^世界而記錄下來(lái)的可鑒別的各種符號(hào)，而信息則是使用者對(duì)數(shù)據(jù)有目的的加工，從而對(duì)接收者的行為或思想產(chǎn)生影響，而不同接收者對(duì)于相同數(shù)據(jù)可能存在不同的解釋和理解。 數(shù)據(jù)是信息的載體，信息是數(shù)據(jù)的目的 “我有一個(gè)好想法，不過(guò)只可意會(huì)不可言傳” 數(shù)據(jù)本身沒(méi)有價(jià)值 用戶不同，數(shù)據(jù)和信息的劃分也不同 數(shù)據(jù)和信息可以相互轉(zhuǎn)化,What is Data?,10535185574,雨認(rèn)會(huì)不天我為明下,0100100101001100 0110111101110110 0110010101011001 0110111101110101,What is Info?我不認(rèn)為明天會(huì)下雨,y=ax-a,01001001 01001100 01101111 01110110 01100101 01011001 01101111 01110101,73 76 111 118 101 89 111 117,I L o v e Y o u,數(shù)據(jù),信息,Recognition,Knowledgement,什么是數(shù)據(jù)庫(kù),在生物信息學(xué)領(lǐng)域，數(shù)據(jù)庫(kù)的主要功能是“存儲(chǔ)”、“管理”以及“檢索”、“調(diào)用” 常見(jiàn)數(shù)據(jù)庫(kù)結(jié)構(gòu)類型：平面文件(FLAT FILE)、關(guān)系型數(shù)據(jù)庫(kù)(R-database)、基于Internet的 XML(Extensible Markup Language),基因是什么,基因是遺傳物質(zhì)的基本單位,基因就是核苷酸序列。 大部分的基因大約是1000-4000個(gè)核苷酸那么長(zhǎng)。 基因通過(guò)控制蛋白質(zhì)的合成，從微觀和宏觀上影響細(xì)胞、組織和器官的產(chǎn)生。 基因在染色體上。,DNA的結(jié)構(gòu),堿基 （腺嘌呤A、鳥(niǎo)嘌呤G、胞嘧啶C、胸腺嘧啶T） 核苷酸,核苷酸是構(gòu)成DNA分子的重要模塊。每個(gè)核苷酸分子由一分子稱作脫氧核糖的戊糖（五碳糖）、一分子磷酸和一分子堿基構(gòu)成。每種核苷酸都有一個(gè)堿基對(duì)，也就是A、T、C、G,DNA序列比對(duì),發(fā)現(xiàn)同源性、相似性 序列同源性：從某一共同祖先經(jīng)過(guò)趨異進(jìn)化而形成的不同序列 序列相似性：指序列比對(duì)過(guò)程中檢測(cè)序列和目標(biāo)序列之間相同堿基或氨基酸殘基序列所占比例的大小 序列比對(duì)定義 序列比對(duì)(Sequence Alignment)就是運(yùn)用某種特定的算法，找出兩個(gè)或多個(gè)序列之間的最大匹配堿基數(shù),動(dòng)態(tài)規(guī)劃與序列比對(duì),基因組數(shù)據(jù)庫(kù)保存了海量的原始數(shù)據(jù)(Raw Data),人類基因有接近30億個(gè)堿基對(duì)。為了查遍所有數(shù)據(jù)并找到其中有意義的關(guān)系，我們便需要依賴于高效的計(jì)算機(jī)科學(xué)字符串算法。 動(dòng)態(tài)規(guī)劃算法是解決最優(yōu)化問(wèn)題的一種高級(jí)的算法技術(shù)，它自下而上尋找子問(wèn)題的最優(yōu)解，從而逐步得到最終問(wèn)題的解。本課程將利用Java實(shí)現(xiàn) 動(dòng)態(tài)規(guī)劃是一種編程思想，并不是實(shí)際的方法。掌握這一思想，適當(dāng)采用遞歸方法，幾乎可以解決所有最優(yōu)解問(wèn)題。 使用動(dòng)態(tài)規(guī)劃兩大條件：最優(yōu)子結(jié)構(gòu)，重疊子問(wèn)題,遞歸(Recursion),在計(jì)算機(jī)程序設(shè)計(jì)中如何理解F(x)=ax+b 編程計(jì)算N！ f(n) = n*f(n-1) n1 編程計(jì)算斐波那契數(shù)列 f(n) = f(n-1)+f(n-2) n2,1, 1, 2, 3, 5, 8 n,動(dòng)態(tài)規(guī)劃,問(wèn)：斐波那契數(shù)列當(dāng)n=5時(shí)，結(jié)果是多少？x=50呢？x=100呢？,當(dāng)遇到重疊子問(wèn)題，即現(xiàn)在正在進(jìn)行遞歸時(shí)函數(shù)的參數(shù)是當(dāng)前已經(jīng)計(jì)算過(guò)的參數(shù)值，那么再進(jìn)行計(jì)算將是重復(fù)計(jì)算。,動(dòng)態(tài)規(guī)劃,利用動(dòng)態(tài)規(guī)劃思想解決之前的問(wèn)題。,public int fib(int n) if ( n = 0) return 0; else if (n=1) return 1; else return fib(n-1)+fib(n-2); ,public int fib1(int n) int table = new int n+1 for(i=0;itable.length;i+) if(i = 0) tablei=0; else if (i=1) tablei=1 else tablei=tablei-2+tablei-1 return tablen ,遞歸解決,動(dòng)態(tài)規(guī)劃解決,動(dòng)態(tài)規(guī)劃算法將已經(jīng)計(jì)算過(guò)的子問(wèn)題的解保存（這里用二維數(shù)組），下一次再需要計(jì)算時(shí)便可以直接提取使用,最長(zhǎng)公共子序列問(wèn)題(LCS),S1：ACTT S2：AGCT,注意該二維數(shù)組賦值的規(guī)律，最右下角的數(shù)值即為這兩個(gè)序列的LCS長(zhǎng)度,遺傳算法,4.1 基本概念 1. 個(gè)體與種群 個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象 （一般就是問(wèn)題的解）的一種稱呼，一個(gè)個(gè) 體也就是搜索空間中的一個(gè)點(diǎn)。 種群(population)就是模擬生物種群而由若 干個(gè)體組成的群體, 它一般是整個(gè)搜索空間 的一個(gè)很小的子集。,2. 適應(yīng)度與適應(yīng)度函數(shù) 適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的 適應(yīng)程度,而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的 表征其優(yōu)劣的一種測(cè)度。 適應(yīng)度函數(shù)(fitness function)就是問(wèn)題中的 全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。 它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算 法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。,3. 染色體與基因 染色體（chromosome）就是問(wèn)題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。 例如： 個(gè)體 染色體 9 - 1001 （2，5，6）- 010 101 110,4. 遺傳操作 亦稱遺傳算子(genetic operator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作: 選擇-復(fù)制(selection-reproduction) 交叉(crossover，亦稱交換、交配或雜交) 變異(mutation，亦稱突變),選擇-復(fù)制 通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xiS的選擇概率P(xi)所決定的選中機(jī)會(huì), 分N次從S中隨機(jī)選定N個(gè)染色體, 并進(jìn)行復(fù)制。,交叉 就是互換兩個(gè)染色體某些位上的基因。,s1=01000101, s2=10011011 可以看做是原染色體s1和s2的子代染色體。,例如, 設(shè)染色體 s1=01001011, s2=10010101, 交換其后4位基因, 即,變異 就是改變?nèi)旧w某個(gè)(些)位上的基因。 例如, 設(shè)染色體 s=11001101 將其第三位上的0變?yōu)?, 即 s=11001101 11101101= s。 s也可以看做是原染色體s的子代染色體。,4.2 基本遺傳算法,算法中的一些控制參數(shù)： 種群規(guī)模 最大換代數(shù) 交叉率(crossover rate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.40.99。 變異率(mutation rate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.00010.1。,分子進(jìn)化與系統(tǒng)發(fā)育,生物大分子進(jìn)化速率相對(duì)恒定,蛋白質(zhì)和核酸等生物大分子在進(jìn)化過(guò)程中氨基酸或核苷酸隨著時(shí)間的替換(改變)數(shù)幾乎是恒定的。,生物大分子進(jìn)化的保守性,對(duì)生物生存制約性大的生物大分子進(jìn)化速度慢 生物大分子內(nèi)部功能區(qū)結(jié)構(gòu)變化速率較慢，而且功能越重要的區(qū)域變化速率越慢 蛋白質(zhì)中越重要的氨基酸變化越慢 結(jié)構(gòu)和化學(xué)性質(zhì)相近的氨基酸之間的替換要比這兩方面不同的氨基酸之間的替換共容易發(fā)生,分子系統(tǒng)發(fā)育樹(shù),如何構(gòu)建系統(tǒng)發(fā)育樹(shù)請(qǐng)參照書(shū)本UPGMA方法實(shí)例 注意要能夠最終畫出系統(tǒng)發(fā)育樹(shù),信息可視化,背景,計(jì)算機(jī)圖形學(xué)的產(chǎn)生和發(fā)展為可視化的誕生奠定基礎(chǔ) 1987年正式將可視化分為：數(shù)據(jù)可視化、信息可視化、科學(xué)可視化,大數(shù)據(jù)時(shí)代的到來(lái)為信息可視化帶來(lái)了新的機(jī)遇和挑戰(zhàn)。,信息可視化模型,RawData,Tables,VIS Structure,Views,Visual Form,Data,可視化結(jié)構(gòu)映射,數(shù)據(jù)轉(zhuǎn)化,視圖轉(zhuǎn)化,Interactions,Data Analysis,信息可視化常用可視化結(jié)構(gòu)（TreeMap）,TreeMap是一種在有限空間里對(duì)分層結(jié)構(gòu)的可視化結(jié)構(gòu)模型。通過(guò)對(duì)形狀大小和顏色的編碼，TreeMap可以非常有效的展現(xiàn)屬性結(jié)構(gòu)中葉子節(jié)點(diǎn)的屬性，可針對(duì)同層次或者不同層次的葉子節(jié)點(diǎn)進(jìn)行比較。充分利用空間。,F（6）,F（5）,F（4）,F（4）,F（3）,F（3）,F（2）,F（3）,F(2),F(2),F(1),F(2),F(1),F(2),F(1),這是我們常見(jiàn)的二叉樹(shù)結(jié)構(gòu)，表示Fib數(shù)列的運(yùn)算過(guò)程,TreeMap,F（6）,F（5）,F（4）,F（4）,F（3）,F（3）,F（2）,F（3）,F(2),F(2),F(1),F(2),F(1),F(2),F(1),F(2),F(2),F(1),F(2),F(2),F(2),F(1),F(1),在TreeMap中，所有的不可分割的矩形塊都是葉子節(jié)點(diǎn)，而這些矩形塊通過(guò)組合構(gòu)成的更大的矩形塊也就是葉子節(jié)點(diǎn)的父節(jié)點(diǎn)，以此類推，從而將整個(gè)樹(shù)形結(jié)構(gòu)呈現(xiàn),信息可視化常用可視化結(jié)構(gòu)（FishEye）,Fisheye的應(yīng)用 Fisheye Menu,魚(yú)眼菜單（Fisheye menus ）對(duì)于幫助用戶瀏覽很長(zhǎng)、但有序的列表很有用處。該菜單可以動(dòng)態(tài)的變換菜單條目的尺寸，將鼠標(biāo)所在區(qū)域放大。這樣便可以在一個(gè)屏幕