計(jì)算機(jī)的計(jì)算能力ppt課件-wenkub
2023-05-18 07:14:55 本頁(yè)面
【正文】 ACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG 生物信息學(xué) 在生物信息的急劇膨脹的壓力下誕生。 生物信息學(xué)熱點(diǎn)問(wèn)題（ 2） ? 后基因組時(shí)期：相互作用－網(wǎng)絡(luò)－功能 – 生物芯片（ DNA芯片、蛋白質(zhì)芯片） – 相互作用網(wǎng)絡(luò) – 調(diào)控網(wǎng)絡(luò) – 藥物設(shè)計(jì) – 。 兩條序列之間的比對(duì) 計(jì)算機(jī)科學(xué)當(dāng)中已經(jīng)有比較成熟的串問(wèn)題的算法 AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC 分子的動(dòng)態(tài)模擬 代謝途徑模擬 計(jì)算在生物問(wèn)題中的角色 實(shí)驗(yàn)產(chǎn)生的龐大生物數(shù)據(jù) 計(jì)算 實(shí)驗(yàn) 專業(yè)領(lǐng)域知識(shí) 理論模型 或假說(shuō) 證實(shí) /新數(shù)據(jù) 合理 設(shè)計(jì) 數(shù)據(jù)挖掘 …. 計(jì)算扮演一個(gè)十分重要的角色 ….. 生物信息學(xué)中的幾個(gè)計(jì)算問(wèn)題 ? 舉例： – Vertex cover – motif finding – DSSP (Distinguishing String Selection Problems) 一、 Vertex cover ? DNA sequences A,G,T,C代表四個(gè) DNA的基本元素 105個(gè)互不相同的 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? ? 問(wèn)題： 105個(gè)基因序列中 ,只去掉 60個(gè) ,使得剩下的序列相似 . ? 模型： – 作一個(gè)圖，每個(gè) DNA串是圖中的一個(gè)點(diǎn)。 – 在圖中找到 60個(gè)點(diǎn)后就沒(méi)有邊了，系統(tǒng)可用 – 如果超過(guò) 60個(gè)點(diǎn)還有邊，系統(tǒng)不可用 ? 問(wèn)題等價(jià)于： 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? ? 另一種說(shuō)法： ? 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個(gè)點(diǎn)拿出來(lái)試一試： 若 n比 60 大得多， ≈n60 實(shí)際中無(wú)法使用，需要對(duì)它進(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)） ? 計(jì)算量為 nk=202220NPhard! ? 改進(jìn)： n5Xn5=n10 2n10 =4n5 n5Xn5=n10 5行 n5 5行 5行 n5 5行 是不是什么問(wèn)題都是單計(jì)算機(jī)可解的？ 例一：求圖 G的最小頂點(diǎn)覆蓋問(wèn)題： 問(wèn)題描述：無(wú)向圖 G=(V,E)的頂點(diǎn)覆蓋是它的頂
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1