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

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