【正文】 7187 DNA repair protein Cystic Fibrosis 219700 CFTR M28668 YCF1 L35237 Metal resistance protein Wilson Disease 277900 WND U11700 CCC2 L36317 Probable copper transporter Glycerol Kinase Deficiency 307030 GK L13943 GUT1 X69049 Glycerol kinase Bloom Syndrome 210900 BLM U39817 SGS1 U22341 Helicase Adrenoleukodystrophy, Xlinked 300100 ALD Z21876 PXA1 U17065 Peroxisomal ABC transporter Ataxia Telangiectasia 208900 ATM U26455 TEL1 U31331 PI3 kinase Amyotrophic Lateral Sclerosis 105400 SOD1 K00065 SOD1 J03279 Superoxide dismutase Myotonic Dystrophy 160900 DM L19268 YPK1 M21307 Serine/threonine protein kinase Lowe Syndrome 309000 OCRL M88162 YIL002C Z47047 Putative IPP5phosphatase Neurofibromatosis, Type 1 162200 NF1 M89914 IRA2 M33779 Inhibitory regulator protein Choroideremia 303100 CHM X78121 GDI1 S69371 GDP dissociation inhibitor Diastrophic Dysplasia 222600 DTD U14528 SUL1 X82022 Sulfate permease Lissencephaly 247200 LIS1 L13385 MET30 L26505 Methionine metabolism Thomsen Disease 160800 CLC1 Z25884 GEF1 Z23117 Voltagegated chloride channel Wilms Tumor 194070 WT1 X51630 FZF1 X67787 Sulphite resistance protein Achondroplasia 100800 FGFR3 M58051 IPL1 U07163 Serine/threoinine protein kinase Menkes Syndrome 309400 MNK X69208 CCC2 L36317 Probable copper transporter 序列比對(duì)的意義 ? 在生物學(xué)的研究中，將未知序列同已知序列進(jìn)行比較分析已經(jīng)成為一種強(qiáng)有力的研究手段 ，生物學(xué)領(lǐng)域中絕大部分的問題在計(jì)算機(jī)科學(xué)領(lǐng)域中主要體現(xiàn)為序列或字符串的問題 。 ?難解的問題！ 比如： SAT, VC, CLIQUE, IS, TSP, ……… ?不可解的問題！ 即：任何計(jì)算機(jī)不論耗費(fèi)多少時(shí)間也不能解的問題。 – 在圖中找到 60個(gè)點(diǎn)后就沒有邊了，系統(tǒng)可用 – 如果超過 60個(gè)點(diǎn)還有邊，系統(tǒng)不可用 ? 問題等價(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? ? 另一種說法： ? 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)拿出來試一試： 若 n比 60 大得多， ≈n60 實(shí)際中無法使用，需要對(duì)它進(jìn)行改進(jìn)。 ?各種生物的 EST序列已達(dá) 600多萬條，其中人類的 EST序列已超過 300 萬條，估計(jì)覆蓋人類基因 90％以上； ?UniGene的數(shù)目約達(dá) 7萬個(gè)；自 1999年初單核苷酸多態(tài)性 ( SNPs,Single Nucleotide Polymorphisms )數(shù)據(jù)庫出現(xiàn)以來，到 2022年 3月 20日 SNP的總數(shù)是 26569，現(xiàn)在已超過 350萬 計(jì)算機(jī)運(yùn)算速度 : 18個(gè)月增長(zhǎng)一倍 。 ?近年來 GenBank中的 DNA堿基數(shù)目呈指數(shù)增加，大約每14個(gè)月增加一倍。 – 這個(gè)圖上的信息量可以用計(jì)算機(jī)來計(jì)算，大約為 10萬的平方。 如：圖靈停機(jī)問題 P類與 NP類問題 P類問題：已找到在 O(nc)時(shí)間求解的確定性算法的問題， c為常數(shù)； NP類問題：若告訴我答案，便可在 O(nc)時(shí)間內(nèi)驗(yàn)證答案是否正確的問題。 如果兩個(gè)序列具有足夠的相似性，則認(rèn)為兩者具有同源性。 得到以下數(shù)據(jù)：遺傳圖、物理圖、全序列圖。 3*109 10,000 books 1 book 100 pages 1 page 3,000 characters CCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGA