2014數(shù)學建模校內(nèi)賽

年“杯”數(shù)學建模競賽 仔細閱讀了數(shù)學建模競賽的競賽規(guī)則知道，別人的成果是競賽規(guī)則的,如果別人的成果或其他公開的資料（包括網(wǎng)上查到的資料，必須按照規(guī)定的參考文獻的表述方式在正文處和參參賽的題目是：“貪“亦有道——基于堿基對匹配校驗的貪婪搜索算法參賽隊員(打印并簽名)：1. 日期： 年4月 “貪“亦有道——基于堿基對匹配校驗的貪婪搜索近年來，隨著計算機計算能力的逐步增強，組逐漸成為計算生物學中非常熱門的研究方向。早期Sanger的技術能夠非常好的解決讀長為500-1000bp的片段的，不過其技術代價高昂[1]。新一代Illumina技術能夠極大地減小測序開支，但是所獲得的讀長較小，一般在300bp以內(nèi)，甚至25-50bp[2]，不過運用新技術指導對序列進行下一步的操作：如果準確率較高，那么可以繼續(xù)進行第二步；12是否在序列12不匹配的序列（DNA重復片評價：最后，引入了兩個指標來評價該算法生成的序列的可靠程度：讀長2匹經(jīng)過數(shù)據(jù)測試，該算法可對Illumina公司Hiseq2000儀產(chǎn)生的讀長片段進行有效的（從500bp的DNA序列的兩頭截取長度為88bp的兩端讀長。最終結(jié)果中，最大讀長達到4007bp，最小讀長長度為501bp，平均讀長為1056bp，序列總長為102800bp，覆蓋率達到85.67%，且每一個序列的驗證率達到85%。2檢背景介是人類探索生命體奧秘的一把，對人類了解應用起到不可估量的作用。近幾年來，隨著技術的飛速發(fā)展，高效率高精度的技術層Sanger（雙脫氧鏈終止法）技術作為第一代技術近幾十年來都是技術的黃金準測。因為其高效低毒的優(yōu)點，Sanger法到飛速的發(fā)展，每18個月效率提高一倍，成本遞減50%[3]。Sanger法能獲得500~1000bp的讀長，但是相對于龐大的組，該方法價格昂貴，耗時較多。自2004年起，新一代技術采用完全不同于Sanger的方法，能夠低成本高效地提供巨量的序列數(shù)據(jù)，獲得大量較短讀長的。以廣泛應用的Illumna的Genomeyzer儀為代表的第二代技術相比于第一代而言，具有讀長短和高通量的特點[4]，短DNA算法應運而生。常見的短DNA 算法的是選取局部最優(yōu)讀長匹配，即前一個片段的前綴與另一個片段的后綴存在足夠長的相同或者相似的序列，當沒有讀長可以延伸的時候終止。SSAKE[5]、VCAKE[6]和SHARCGS[7]都是常見的貪心法方法。圖算法主要包括三個步驟：利用所有片段相互比對構(gòu)建列表、依據(jù)信息建立圖、分析圖可能的路徑信息尋找最優(yōu)路徑。當短序列涉及節(jié)點信息較多時，上述方法存在一定的局限性。魯因圖法的算法是以K-mer為基本單位構(gòu)建圖，利用圖的結(jié)構(gòu)特征對其中包含如Velvet[8]短序列組裝工具。模型假一、假設：切片長度lp有10%的誤差。即lp,maxlp(110%)5001.1550bplp,minlp(110%)5000.9原因 觀察到，如 切片長度恰好等于500bp，那么讀長R1k所對應的讀二、假設：實際讀長長度lr,real=100bp，觀測讀長88bp為實際讀長100bp中截取所原因：查詢儀Hiseq2000的規(guī)格[9]，應為2100bp配置參數(shù)說 鏈??中讀長??取值范圍 ??????(??1, 允許拼接??1,??1 ??????(??1, 模型建11221圖2鏈1和鏈2中堿基和質(zhì)量值的分布 NDef:S1{R1,R1,L, NS2{R2,R2,L,

Q1Q1 ,L, k k Q2Q2, ,L k k 得到處理后有效樣本數(shù)Neff。fori1:ifp1,p20&p2p1i,

,i,,

2||

i,

,

i,p2 B-tail是需要在與處理中排除掉的，否則將會給后續(xù)的序列組裝工作引入誤差。fori1:i, i,ifp0，s.t. 2，theni, i,ifp0，s.t.Q2i,p2，thensetB2i,pDefsim(R1R1為鏈1上讀長ijR1R1 ii

sim(R1,R1

1RjRR1

= , j CTTGCTAGCGTAGGTCTGiiiRandomlychooseR1fromiforj1:Neff\

,SEQpickjargmaxsim(R1,R1)&sim(R1,R1) 將選出的讀長與原序列拼接（拼接規(guī)則見上述例子 SEQR1 R1R2（ 圖3讀長R1k,R2k的關 kDefdis(R1R2為鏈1上讀長k與鏈2相應讀長kR21首端與 k 有338 2 dis(R1 如果檢測不存在，那 認為當前的序列是“潛在錯誤的置 i 在貪婪延伸的過程中，重合度sim(R1R1 度高的拼接（兩段讀長重復長度更長）合度低的拼接度更高。從宏觀角度，更長的重復長度意味著組成總序列的讀長個數(shù)。因此，定義序列平均讀長覆蓋長L 序列長 拼接序列的讀（列就越可靠。因此，定義驗證率V驗證通過的讀長數(shù) 總驗證次R1k重新放入可用讀長集合，使得R1k可以用于其他序列的貪婪延伸過程。模型結(jié)4個步驟）535396%2124%。4數(shù)據(jù)說明，按照簡單的貪婪拼接獲得的序列，只有很少部分能夠通過步驟4的檢5可靠序列的驗證率6證的序列中，驗證率超過0.85的序列總長為102800bp，接近原DNA總長度覆蓋率為85.67%，平均讀長為1056bp。7滿足驗證率????

8 該模型的時間復雜度O(N2logN),空間復雜度為O(N *m)，其中m為單個讀長長度88bp， 模型評針對采用Hiseq2000儀進序后所得的細菌人工BAC的序列，重組后的序列長度達到102800，對于全長約120000的細菌人工DNA來說，覆蓋率達到85.67%，平均序列長度為1056bp，最大讀長達到4007bp。采用鏈2的讀長檢驗拼接序列增加了結(jié)果的可靠程度?？梢钥吹?，采用驗證率Vp利用簡單的數(shù)據(jù)預處理和后處理，損失了一些可以利用的讀長。僅僅將質(zhì)量值為結(jié)Illumina公司Hiseq2000儀產(chǎn)生的細胞人工BAC讀長片段上對的序列總長為102800bp，覆蓋率達到85.67%，且每一個序列的驗證率達到85%。于500bp的序列（驗證率為0，該模型并沒有很好地給出衡量標準。針對短序列如何驗參考文[1].BentleyDR,Whole-genomere-sequencing[J],CurrentOpinionGeneticsandDevelopment,16(6):545-52,2006[2].，盧志遠，等，面向新一代組技術的序列拼接算法，生物信息83期，20109月[3].石子倫，，新一代技術簡介及其在細菌組流行病學的應用，應用預防醫(yī)學，2013年01期[4].MarguliesM,EgholmM,AltmanWEetal,Genomesequencinginmicrofabricatedhigh-densitypicolitrereactors[J],Nature,437(7057):376-80,2005Sep15[5].WarrenRL,SuttonGG,etal,AssemblingmillionsofshortDNAsequencesusingSSAKEBioinformatics,23(4)：500-1,2007Feb[6].JeckWR,ReinhardtJA,etal,ExtendingassemblyofshortDNAsequencestohandleerror[J],Bioinformatics,23(21):2942-4,2007Nov1[7].DohmJC,LottazC,etal,SHARCGS,afastandhighlyaccurateshort-readassemblyalgorithmfordenovogenomicsequencing,GenomeRes.,17(11):1697-706,2007[8].ZerbinoDR,BirneyE,Velvet:algorithmsfordenovoshortreadassemblyusingdeBruijngraphs,GenomesRes.,18(5):821-9,2008May[9].Illumina,Inc.HiSeqTMSequencing /s/systems/hiseq/datasheethiseqsystems.pdf,