生物信息學期末考試重點

生物信息學期末考試重點生物信息學期末考試重點生物信息學期末考試重點生物信息學期末考試重點編制僅供參考審核批準生效日期地址：電話：傳真:郵編:第一講生物信息學（Bioinformatics）是20世紀80年代末隨著人類基因組計劃的啟動而興起的一門新型交叉學科，它體現(xiàn)了生物學、計算機科學、數(shù)學、物理學等學科間的滲透與融合。生物信息學通過對生物學實驗數(shù)據(jù)的獲取、加工、存儲、檢索與分析，達到揭示數(shù)據(jù)所蘊含的生物學意義從而解讀生命活動規(guī)律的目的。生物信息學不僅是一門學科，更是一種重要的研究開發(fā)平臺與工具，是今后進行幾乎所有生命科學研究的推手。生物技術(shù)與生物信息學的區(qū)別及聯(lián)系生物技術(shù)生物信息學英文名稱BiotechnologyBioinformatics最終目的產(chǎn)品研究方法利用生物的特性和功能，設(shè)計構(gòu)建具有預期功能的新物質(zhì)或品系對生物信息進行采集、處理、存儲、分析和解釋涉及學科基因工程、分子生物學、生物化學、遺傳學、細胞生物學、胚胎學、免疫學等生物學、計算機科學、數(shù)學、物理學等發(fā)展歷程可追溯到2000B.C.數(shù)十年生物信息學的發(fā)展歷史人類基因組計劃（HGP）人類基因組計劃由美國科學家于1985年提出，1990年啟動。根據(jù)該計劃，在2015年要把人體約4萬個基因的密碼全部揭開，同時繪制出人類基因的譜圖，也就是說，要揭開組成人體4萬個基因的30億個堿基對的秘密。HGP與曼哈頓原子彈計劃和阿波羅計劃并稱為三大科學計劃，被譽為生命科學的登月計劃。(百度百科)隨著基因組計劃的不斷發(fā)展，海量的生物學數(shù)據(jù)必須通過生物信息學的手段進行收集、分析和整理后，才能成為有用的信息和知識。換句話說，人類基因組計劃為生物信息學提供了興盛的契機。上文所說的基因、堿基對、遺傳密碼子等術(shù)語都是生物信息學需要著重研究的地方。第二講回顧細胞結(jié)構(gòu)細胞是所有生命形式結(jié)構(gòu)和功能的基本單位細胞組成細胞膜主要由脂類和蛋白質(zhì)組成的環(huán)繞在細胞表面的雙層膜結(jié)構(gòu)細胞質(zhì)細胞膜與細胞核之間的區(qū)域：包含液體流質(zhì)，夾雜物存儲的營養(yǎng)、分泌物、天然色素和細胞器細胞器細胞內(nèi)完成特定功能的結(jié)構(gòu)：線粒體、核糖體、高爾基體、溶酶體等細胞核最大的細胞器DNA的結(jié)構(gòu)堿基（腺嘌呤A、鳥嘌呤G、胞嘧啶C、胸腺嘧啶G）核苷酸核苷酸是構(gòu)成DNA分子的重要模塊。每個核苷酸分子由一分子稱作脫氧核糖的戊糖（五碳糖）、一分子磷酸和一分子堿基構(gòu)成。每種核苷酸都有一個堿基對，也就是A、T、C、G基因是什么基因是遺傳物質(zhì)的基本單位基因就是核苷酸序列。大部分的基因大約是1000-4000個核苷酸那么長?；蛲ㄟ^控制蛋白質(zhì)的合成，從微觀和宏觀上影響細胞、組織和器官的產(chǎn)生。基因在染色體上。第四講數(shù)據(jù)結(jié)構(gòu)及其對應算法數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)探討的是在計算機中如何有效地存放數(shù)據(jù)，使其可以方便地被處理二維數(shù)組鏈表棧和隊列第五講序列比較序列比較的根本任務是：發(fā)現(xiàn)序列之間的相似性辨別序列之間的差異目的： 相似序列相似的結(jié)構(gòu)，相似的功能 判別序列之間的同源性 推測序列之間的進化關(guān)系序列對比定義:序列對比(sequencealignment)是運用某種特定的數(shù)學模型或算法，找出兩個或多個序列之間的最大匹配堿基或殘基數(shù)，比對的結(jié)果反映了算法在多大程度上提供序列之間的相似性關(guān)系及他們的生物學特征。編輯距離...AGCACAC--A......A--CACACTA...-Match（a，a）字符匹配-Delete（a，-）從第一條序列刪除一個字符，或者在第二條序列相應的位置插入空位-Replace（a，b）以第二條序列中的字符b替換第一條序列中的字符a,a不等于b-Insert（-，b）在第一條序列插入空位符，或者刪除第二條序列中的對應字符b編輯距離，又稱Levenshtein距離，是指在對于兩個字符串，由其中一個轉(zhuǎn)換成另一個所需要的最少編輯次數(shù)，該編輯可以是Replace,Delete,InsertBesting－－＞BeatenS1.Replace(s->a)S2.Replace(i->e)S3.Delete(g->-)S3.Insert (-,g)問題：把一個字符串s1最少經(jīng)過多少步操作變成字符串s2

相關(guān)算法遞歸函數(shù)調(diào)用自身，需要有邊界函數(shù)n!=n(n-1)(n-2)...1;f(n)=f(n-1)+f(n-2)動態(tài)規(guī)劃（最長公共字符子序列）將大問題分解為一系列子問題，每個子問題的解保存在數(shù)組中用來求最終解[問題描述]字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。最長公共字符子序列A=“a0，a1，…，am-1”；B=“b0，b1，…，bm-1”；Z=“z0，z1，…，zk-1”為它們的最長公共子序列，那么關(guān)于A,B,Z應該有如下性質(zhì)：1）如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列；2）如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列；3）如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。最長公共字符子序列 現(xiàn)有兩個序列X={x1,x2,x3，...xi}，Y={y1,y2,y3，....，yj}，設(shè)一個C[i,j]:保存Xi與Yj的LCS的長度。第六講編輯距離問題算法ifi==0且j==0，matrix(i,j)=0ifi==0且j>0，matrix(i,j)=jifi>0且j==0，matrix(i,j)=iif

i≥1

且

j≥1，matrix(i,j)==min{matrix(i-1,j)+1,matrix(i,j-1)+1,matrix(i-1,j-1)+f(i,j)}，當?shù)谝粋€字符串的第i個字符不等于第二個字符串的第j個字符時，f(i,j)=1；否則，f(i,j)=0。第八講全局序列比對算法Levenshtein與LCS的異同點 S[i-1,j-1]+cost(ai,bj)cost=0||1S[i,j]=min S[i-1,j]+cost(ai,-) delete(i,-) S[i,j-1]+cost(-,bj) delete(j,-)算法Demo A B B A 0 1 2 3 4B 1 1 1 2 3B 2 2 1 1 2A 3 2 2 2 1第九講生物信息學的計算機、統(tǒng)計學及數(shù)學基礎(chǔ)生物信息學的定義：生物信息學是生物學與計算機科學以及應用數(shù)學等學科相互交叉而形成的一門新興學科。因此，計算機技術(shù)將是進行生物信息學研究的重要手段;而數(shù)學知識是研究的重要方法。目前，一般提到的"生物信息學"是就指這個狹義的概念，更準確地說，應該是分子生物信息學（MolecularBioinformatics）。2、動態(tài)規(guī)劃方法動態(tài)規(guī)劃（DynamicProgramming）是一種解決多階段決策過程的最優(yōu)化方法或復雜空間的優(yōu)化搜索方法動態(tài)規(guī)劃解決問題的基本過程是：將一個問題的全局解分解為局部解，逆序遞推求出局部最優(yōu)解，隨著執(zhí)行過程的推進，“局部”逐漸接近“全局”，最終獲得全局最優(yōu)解在生物信息學中，使用得最多的是反向傳播神經(jīng)網(wǎng)絡(luò)（BackPropagationNeuralNetwork，簡稱BP網(wǎng)）。專家系統(tǒng)專家系統(tǒng)（ExpertSystem）是一種基于知識的智能系統(tǒng)，它將領(lǐng)域?qū)＜业慕?jīng)驗用一定的知識表示方法表示出來，并放入知識庫中，供推理機使用知識庫是專家系統(tǒng)的第一重要組成部分，知識庫中的知識通常分為兩類：一類領(lǐng)域的事實性知識或廣泛公用的知識另一類是啟發(fā)性知識，是該領(lǐng)域?qū)＜以陂L期研究和實踐過程中積累起來的經(jīng)驗總結(jié)知識獲取方式大致上可以分為兩種：一種是由知識工程師向領(lǐng)域?qū)＜以儐栍嘘P(guān)知識，經(jīng)過整理編輯后將知識轉(zhuǎn)換成計算機表示形式，送入知識庫另一種是針對大量數(shù)據(jù)進行機器學習，分析、總結(jié)和抽取出有用的新知識，這是更高層次的知識獲取方式。專家系統(tǒng)的另一個重要部分是推理機，由它來控制和協(xié)調(diào)整個系統(tǒng)，并根椐當前輸入的數(shù)據(jù)和知識，按一定的推理策略，去解決當前的問題，推導出結(jié)論。第十講數(shù)據(jù)挖掘數(shù)據(jù)挖掘（定義） 從技術(shù)層面上：數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中提取有用信息的過程從商業(yè)層面上：數(shù)據(jù)挖掘就是一種商業(yè)信息處理技術(shù)，通過對大量業(yè)務數(shù)據(jù)進行抽取、轉(zhuǎn)換、分析和建模處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)數(shù)據(jù)挖掘（任務）分類分析（Classification）通過分析示例數(shù)據(jù)庫中的數(shù)據(jù)，為每個類別做出準確的描述或建立分析模型產(chǎn)生分類規(guī)則，然后用這個模型或規(guī)則對數(shù)據(jù)庫中的其他記錄進行分類。已被廣泛應用于用戶行為分析、生物科學等領(lǐng)域。聚類分析（Clustering）聚類和分類是兩個容易混淆的概念。聚類是一種無指導的觀察式學習，沒有預先定義的類。而分類問題是有指導的示例式學習，預先定義類。分類是訓練樣本里包含有分類屬性值，而聚類是要在訓練樣本中發(fā)現(xiàn)這些分類屬性值。第十一講動態(tài)規(guī)劃矩陣相乘 只有當矩陣A的列數(shù)與矩陣B的行數(shù)相等時A×B才有意義。一個m×n的矩陣a(m,n)左乘一個n×p的矩陣b(n,p)，會得到一個m×p的矩陣c(m,p)共計算2*3*4=24次動態(tài)規(guī)劃算法確定要用動態(tài)規(guī)劃算法之后如何去分析問題怎么描述問題，要把問題描述為交疊的子問題交疊子問題的初始條件（邊界條件）動態(tài)規(guī)劃在形式上往往表現(xiàn)為填矩陣的形式回顧編輯距離或者LCS算法，以上三點也都在我們的分析中體現(xiàn)背包問題背包問題簡述問題：如何在不超出背包重量的前提下得到最大價值？思考解決問題的結(jié)構(gòu)，尋找最優(yōu)子結(jié)構(gòu)Item{a1,a2,a3}W:{5,3,2}P:{9,7,8}MaxWeight:5W:{5,3,2}P:{9,7,8}MaxWeight:5問題：一共要計算多少種可能性？核心算法 c[i][m]=max{c[i-1][m],c[i-1][m-w[i]]+p[i]}第十四講信息可視化技術(shù)背景計算機圖形學的產(chǎn)生和發(fā)展為可視化的誕生奠定基礎(chǔ)1987年正式將可視化分為：數(shù)據(jù)可視化、信息可視化、科學可視化數(shù)據(jù)可視化將數(shù)據(jù)以圖像的形式呈現(xiàn)出來數(shù)據(jù)可視化主要旨在借助于圖形化手段，清晰有效地傳達與溝通信息。數(shù)據(jù)可視化是關(guān)于數(shù)據(jù)之視覺表現(xiàn)形式的研究；其中，這種數(shù)據(jù)的視覺表現(xiàn)形式被定義為一種以某種概要形式抽提出來的信息，包括相應信息單位的各種屬性和變量。數(shù)據(jù)可視化技術(shù)的基本思想是將數(shù)據(jù)庫中每一個數(shù)據(jù)項作為單個圖元元素表示，大量的數(shù)據(jù)集構(gòu)成數(shù)據(jù)圖像，同時將數(shù)據(jù)的各個屬性值以多維數(shù)據(jù)的形式表示，可以從不同的維度觀察數(shù)據(jù)，從而對數(shù)據(jù)進行更深入的觀察和分析?；靖拍罴皹?gòu)成元素數(shù)據(jù)空間：由n維屬性和m個元素組成的數(shù)據(jù)集所構(gòu)成的多維信息空間數(shù)據(jù)開發(fā)：利用一定的算法和工具對數(shù)據(jù)進行定量的推演和計算數(shù)據(jù)分析：指對多維數(shù)據(jù)進行切片、塊、旋轉(zhuǎn)等動作剖析數(shù)據(jù)，從而能多角度多側(cè)面觀察數(shù)據(jù)數(shù)據(jù)可視化：