亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于分治算法的DNA序列比對成本模型

        2019-04-28 05:59:36劉欣睿四川大學軟件學院
        數(shù)碼世界 2019年3期
        關(guān)鍵詞:信息學復(fù)雜度動態(tài)

        劉欣睿 四川大學軟件學院

        引言

        DNA序列比對是生物信息學中的一項重要任務(wù),在實際應(yīng)用中,DNA序列比對可用于DNA親代測試,同時有助于了解物種和個體差異之間的變化。本文將提供最佳的DNA序列比對,旨在減少任何給定序列的缺失匹配和缺口的數(shù)量。算法實現(xiàn)的第一個挑戰(zhàn)是巨大的搜索空間,因此本文建立了優(yōu)化數(shù)學模型以修剪搜索方法。其次,不能用蠻力來找到比較的最佳方法。綜上本文算法基于這兩個挑戰(zhàn)而引入。

        1 分治算法

        對于分治算法需要確定何時退出遞歸。例如,對于兩個DNA序列:X(0,m)和Y(0,n),如果要計算opt(i,j),那么遞歸的退出可以分為兩種情況:

        但該算法存在兩個缺陷。首先,該算法僅提供最佳成本懲罰,而不是最佳對齊。其次,算法的復(fù)雜度非常大并且呈指數(shù)增長,在最壞的情況下,該算法的時間復(fù)雜度將為O(3 ^ max(m,n))。

        2 動態(tài)規(guī)劃算法

        為克服上述分治算法的缺陷,本文引入動態(tài)規(guī)劃算法。在設(shè)計動態(tài)規(guī)劃算法時,通??梢宰裱韵聨讉€步驟:

        1.分析和比較最優(yōu)解的特征;

        2.遞歸定義最優(yōu)值;

        3.通過自上而下的邏輯運算得到最優(yōu)解,得到函數(shù)的最大值或最小值。

        這種方法是以時間交換空間。首先,建立一個m乘n的矩陣。然后將opt(i,j)的結(jié)果存儲到第i行第j列。例如,設(shè)有兩個DNA序列 X(0,10)和 Y(0,8):

        根據(jù)遞歸的終止條件,可以得出以下結(jié)論:

        3 算法實現(xiàn)結(jié)果

        由上述算法原理可進一步實現(xiàn)動態(tài)規(guī)劃算法,最終得到已知DNA序列的成本矩陣11*9,如下所示:

        i/j 0T 1A 2A 3G 4G 5T 6C 7A 8 -0A 7 8 10 12 13 15 16 18 201A 6 6 8 10 11 13 14 16 182C 6 5 6 8 9 11 12 14 163A 7 5 4 6 7 9 11 12 144G 9 7 5 4 5 7 9 10 125T 8 8 6 4 4 5 7 8 106T 9 8 7 5 3 3 5 6 87A 11 9 7 6 4 2 3 4 68C 13 11 9 7 5 3 1 3 49C 14 12 10 8 6 4 2 1 210- 16 14 12 10 8 6 4 2 0

        根據(jù)上述矩陣,已知array [0] [0]=7,即可利用tracepath來獲得最佳對齊。

        (1)如果(0,1)屬于路徑,則 opt(0,0)= opt(0,1)+ 2 = 6+ 2 = 8> 7,因此這種情況不會退出。

        (2)如果(0,1)屬于路徑,則 opt(0,0)= opt(1,0)+ 2 = 8+ 2 = 10> 7,因此這種情況不會退出。(x0與a對齊間隙)

        (3)如果(1,1)屬于路徑,則 opt(0,0)= opt(1,1)+ 1 = 6 +1 = 7,因此本情況是最佳對齊。(x0與y0對齊,但是x0與y0不匹配)

        4 結(jié)論

        序列比對是生物信息學中最基本的問題。為了進一步研究DNA序列比對問題,本文建立了一個新模型,稱為成本模型,以確定比對優(yōu)化的程度?;谶@個新模型,使用Divide and Conquer算法來解決這個問題。但本文選擇動態(tài)規(guī)劃算法來克服時間復(fù)雜性的缺陷。最后,創(chuàng)建了后向跟蹤算法,以找到最佳對齊的軌跡。

        猜你喜歡
        信息學復(fù)雜度動態(tài)
        國內(nèi)動態(tài)
        國內(nèi)動態(tài)
        國內(nèi)動態(tài)
        雞NRF1基因啟動子區(qū)生物信息學分析
        動態(tài)
        一種低復(fù)雜度的慣性/GNSS矢量深組合方法
        初論博物館信息學的形成
        中國博物館(2018年2期)2018-12-05 05:28:50
        求圖上廣探樹的時間復(fù)雜度
        某雷達導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進
        出口技術(shù)復(fù)雜度研究回顧與評述
        2020久久精品亚洲热综合一本| 国产精品区一区二区三在线播放| 正在播放老肥熟妇露脸| 中国凸偷窥xxxx自由视频妇科| 国产精品久久久久久久久免费观看| 熟妇与小伙子露脸对白| 人妻少妇偷人精品视频| 蜜桃视频免费进入观看| 一本色道久久88综合日韩精品| 99久久免费精品高清特色大片| 乱色视频中文字幕在线看| 视频一区视频二区亚洲| 国产亚洲av看码精品永久| 国产精品成人3p一区二区三区| 久久久久久国产精品美女| 无码人妻丝袜在线视频| 美女把内衣内裤脱了给男人舔| 森中文字幕一区二区三区免费| 曰本女人与公拘交酡| 中出内射颜射骚妇| 狠狠色欧美亚洲综合色黑a| 日本一区二区视频免费在线观看| 丰满人妻久久中文字幕| 私人毛片免费高清影视院| 国产精品自产拍在线18禁| 极品少妇被后入内射视| 国产亚洲熟妇在线视频| av免费不卡国产观看| 免费看久久妇女高潮a| 亚洲国产日韩欧美高清片a| 丰满人妻被公侵犯的视频| 亚洲精品久久国产精品| 成人免费一区二区三区| 久久久久久99精品| 热综合一本伊人久久精品| 日韩性爱视频| 日韩免费无码一区二区三区| mm在线精品视频| 蜜桃在线高清视频免费观看网址 | 国产成人精品日本亚洲专区6| 国产91精品清纯白嫩|