中國科技大學系列生物信息學

1、會計學1中國科技大學系列生物信息學中國科技大學系列生物信息學第1頁/共79頁第2頁/共79頁第3頁/共79頁第4頁/共79頁r 功能同源的蛋白質(zhì)功能同源的蛋白質(zhì) 通過中性進化，引入可接受的點突通過中性進化，引入可接受的點突變；變；r 進化模型：進化模型： A. 基本假設：中性進化，基本假設：中性進化，Kimura,1968; B. 進化的對稱性進化的對稱性: A-B = B-A; C. 擴展性：通過對較短時間內(nèi)氨基酸替代關系的計算來計算擴展性：通過對較短時間內(nèi)氨基酸替代關系的計算來計算較長時間的氨基酸替代關系；較長時間的氨基酸替代關系；第5頁/共79頁第6頁/共79頁第7頁/共79頁第8頁/共

2、79頁家族一家族一家族二家族二家族三家族三F K IL KIIF F FK IF K KF K I K KIIFIFK IF L KF FIL LI K F F LK L F K LF FI K LI K FILK L F L L第9頁/共79頁FKILKFKIKKFKIKKFFIKLFFILLFFIKL(LK)(KF)(LK)(LK)第10頁/共79頁KFILK116F121I121L611第11頁/共79頁1002iifim總替換數(shù)總共發(fā)生替換數(shù)氨基酸第12頁/共79頁iiiiijmmjijjimmji1時，總共發(fā)生替換數(shù)氨基酸相互替換的次數(shù)與氨基酸時，第13頁/共79頁原氨基酸原氨基酸K

3、FIL替換氨基替換氨基酸酸K0.98750.0015630.0015630.009375F0.0013890.9944440.0027780.001389I0.0017860.0035710.9928570.001786L0.01250.0020830.0020830.983333第14頁/共79頁)/lg(10iijijfmr第15頁/共79頁KFILK6F-235I-22-196L-13-22-207第16頁/共79頁KFILK6F-205I-19-166L-10-19-187第17頁/共79頁第18頁/共79頁第19頁/共79頁第20頁/共79頁第21頁/共79頁第22頁/共79頁)/(

4、lg22eqrij第23頁/共79頁第24頁/共79頁序列相似性序列相似性 %999080706050403020PAM數(shù)值數(shù)值11123385680112159246BLOSUM數(shù)值數(shù)值908062-45第25頁/共79頁第26頁/共79頁Made by GENEDOC第27頁/共79頁GapVDSCYGap0-11-22-33-44-55V-114-7-18-29-40E-22-76-5-16-27S-33-18-510-1-12L-44-29-16-19-3C-55-40-27-1287Y-66-51-38-23-31542時間復雜度：時間復雜度：O(n2)第28頁/共79頁三條序列：時

5、間復雜度：三條序列：時間復雜度：O(lmn) = O(n3)四條序列：時間復雜度：四條序列：時間復雜度：O(n4)，非多項式時間！，非多項式時間！多項式時間復雜度要求：O(n3)m條序列：時間復雜度：條序列：時間復雜度：O(nm)，NPC問題問題！第29頁/共79頁第30頁/共79頁Sequence ASequence BSequence C 搜索有限空間，類似于搜索有限空間，類似于BLAST算法算法第31頁/共79頁第32頁/共79頁最優(yōu)的多序列比對最優(yōu)的多序列比對非最優(yōu)的雙序列比對非最優(yōu)的雙序列比對第33頁/共79頁第34頁/共79頁第35頁/共79頁第36頁/共79頁第37頁/共79頁第

6、38頁/共79頁第39頁/共79頁兩兩比對，構(gòu)建距離矩陣指導樹的構(gòu)建指導樹的構(gòu)建漸進比對漸進比對第40頁/共79頁每條序列的權(quán)值每條序列的權(quán)值Score:BLOSUM62的分數(shù)的分數(shù)第41頁/共79頁第42頁/共79頁第43頁/共79頁第44頁/共79頁第45頁/共79頁GeneDocGeneDoc軟件，導入軟件，導入.aln.aln文件文件第46頁/共79頁第47頁/共79頁第48頁/共79頁第49頁/共79頁第50頁/共79頁同時進行全局和局部的雙序列比同時進行全局和局部的雙序列比對對對以上打分的結(jié)果設計權(quán)重系統(tǒng)，對以上打分的結(jié)果設計權(quán)重系統(tǒng)，找到序列中最保守的部分找到序列中最保守的部分漸

7、進方法的比對，基于上述計算的漸進方法的比對，基于上述計算的primary library第51頁/共79頁第52頁/共79頁Seq1: ARKCVSeq2: ARCVSeq3: AKCVARKCVAR-CVA-KCVARKCVA-RCVA-KCVARKCVAR-CVAK-CV第53頁/共79頁第54頁/共79頁1. 1. 先用先用“漸進漸進”算法進行多序列比算法進行多序列比對對; ;2. 2. 基于多序列比對的結(jié)果構(gòu)建進化基于多序列比對的結(jié)果構(gòu)建進化樹；樹；3. 3. 重新計算序列之間的距離，再用重新計算序列之間的距離，再用“漸進漸進”算法進行多序列比對；算法進行多序列比對；4. 4. 重復上

8、述步驟，直到結(jié)果不再發(fā)重復上述步驟，直到結(jié)果不再發(fā)生改變?yōu)橹?。生改變?yōu)橹?。?5頁/共79頁第56頁/共79頁第57頁/共79頁第58頁/共79頁第59頁/共79頁第60頁/共79頁第61頁/共79頁第62頁/共79頁第63頁/共79頁第64頁/共79頁第65頁/共79頁第66頁/共79頁第67頁/共79頁第68頁/共79頁第69頁/共79頁第70頁/共79頁第71頁/共79頁KFILK6F-205I-19-166L-10-19-187第72頁/共79頁第73頁/共79頁Made by GENEDOC第74頁/共79頁三條序列：時間復雜度：三條序列：時間復雜度：O(lmn) = O(n3)四條序列：時間復雜度：四條