計算機(jī)的計算能力ppt課件-wenkub
2023-05-18 07:14:55 本頁面
【正文】 ACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG 生物信息學(xué) 在生物信息的急劇膨脹的壓力下誕生。 生物信息學(xué)熱點(diǎn)問題（ 2） ? 后基因組時期：相互作用－網(wǎng)絡(luò)－功能 – 生物芯片（ DNA芯片、蛋白質(zhì)芯片） – 相互作用網(wǎng)絡(luò) – 調(diào)控網(wǎng)絡(luò) – 藥物設(shè)計 – 。 兩條序列之間的比對 計算機(jī)科學(xué)當(dāng)中已經(jīng)有比較成熟的串問題的算法 AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC 分子的動態(tài)模擬 代謝途徑模擬 計算在生物問題中的角色 實(shí)驗產(chǎn)生的龐大生物數(shù)據(jù) 計算 實(shí)驗 專業(yè)領(lǐng)域知識 理論模型 或假說 證實(shí) /新數(shù)據(jù) 合理 設(shè)計 數(shù)據(jù)挖掘 …. 計算扮演一個十分重要的角色 ….. 生物信息學(xué)中的幾個計算問題 ? 舉例： – Vertex cover – motif finding – DSSP (Distinguishing String Selection Problems) 一、 Vertex cover ? DNA sequences A,G,T,C代表四個 DNA的基本元素 105個互不相同的 DNA序列 G A T T C C A G T…………………………………… ? Give n(here,n= 105) DNA sequences, can you find 60 of them whose remove makes the remaining sequences consistent? ? 問題： 105個基因序列中 ,只去掉 60個 ,使得剩下的序列相似 . ? 模型： – 作一個圖，每個 DNA串是圖中的一個點(diǎn)。 – 在圖中找到 60個點(diǎn)后就沒有邊了，系統(tǒng)可用 – 如果超過 60個點(diǎn)還有邊，系統(tǒng)不可用 ? 問題等價于： Give a graph ,can you find 60 vertices whose remove makes the graph has no edge? ? Vertex cover(點(diǎn)覆蓋 ):Give a graph, can you find k vertices such that each edge has at least one end in these k vertices? ? 另一種說法： ? Give a graph G of n vertices , decide if there are k vertices whose remove makes the graph edgeless. ? Try any subset of 60 vertices and check if it make a vertex cover(點(diǎn)覆蓋 ) ? 圖中每 60個點(diǎn)拿出來試一試： 若 n比 60 大得多， ≈n60 實(shí)際中無法使用，需要對它進(jìn)行改進(jìn)。 ? Give k DNA sequences,find a pattern of length 15 that is similar to a subsequence in each sequence. ? Give a kpartile graph,find a set of vertices,one from each row,such that all these k vertices are connected.（ 最大團(tuán)） ? 計算量為 nk=202220NPhard! ? 改進(jìn)： n5Xn5=n10 2n10 =4n5 n5Xn5=n10 5行 n5 5行 5行 n5 5行 是不是什么問題都是單計算機(jī)可解的？ 例一：求圖 G的最小頂點(diǎn)覆蓋問題： 問題描述：無向圖 G=(V,E)的頂點(diǎn)覆蓋是它的頂
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1