本文選題：串聯(lián)重復(fù)體 + LZ分解��； 參考：《西安電子科技大學(xué)》2009年碩士論文

【摘要】：在DNA序列分析中,串聯(lián)重復(fù)體查找是一個(gè)重要的基礎(chǔ)性問題。人類DNA序列50%以上是由串聯(lián)重復(fù)體組成的。串聯(lián)重復(fù)體在基因表達(dá)、調(diào)控和遺傳等方面起著十分重要的作用,同時(shí)它是產(chǎn)生多種疾病的病因。另外以串聯(lián)重復(fù)體為基礎(chǔ)的“DNA指紋技術(shù)”在法醫(yī)學(xué)等領(lǐng)域廣泛應(yīng)用。因此關(guān)于串聯(lián)重復(fù)的研究具有十分重要的意義。本文主要研究串聯(lián)重復(fù)體查找算法。 1)針對精確串聯(lián)重復(fù)體提出了一種基于LZ分解查找串聯(lián)重復(fù)體的算法。對于存儲在后綴樹上的字符串S,該算法能在線性的時(shí)間找到所有出現(xiàn)在S中的串聯(lián)重復(fù)體。為了進(jìn)一步提高算法的效率,我們對后綴樹進(jìn)行了改進(jìn),給中間節(jié)點(diǎn)加入了葉子信息數(shù)組,這樣就避免了算法對子樹的遍歷。 2)引入了一種新類型的近似串聯(lián)重復(fù)體—進(jìn)化串聯(lián)重復(fù)體,由于以前提出的算法都不能解決進(jìn)化串聯(lián)重復(fù)體的查找問題,因此提出了基于海明距離的查找算法。對于給定的重復(fù)單元的長度l,該算法的時(shí)間復(fù)雜度為O(ln2),解決了進(jìn)化串聯(lián)重復(fù)體的查找問題。 為了說明算法的正確性和有效性,本文將這兩種分別應(yīng)用于實(shí)際的基因組DNA序列,結(jié)果表明基于LZ分解的查找串聯(lián)重復(fù)體方法能找到更多的串聯(lián)重復(fù)體,基于海明距離的查找方法則解決了進(jìn)化串聯(lián)重復(fù)體的查找問題。
[Abstract]:In DNA sequence analysis, tandem repeat finding is an important basic problem. More than 50% of human DNA sequences are composed of tandem repeats. Tandem repeats play an important role in gene expression, regulation and heredity. In addition, DNA fingerprinting based on tandem repeats is widely used in forensic science and other fields. Therefore, the study of tandem repetition is of great significance. In this paper, we mainly study the algorithm of tandem repeat lookup. 1) an algorithm based on LZ decomposition is proposed to find the exact tandem repeats. For the string S stored in the suffix tree, the algorithm can find all concatenated repeating bodies in S at linear time. In order to further improve the efficiency of the algorithm, we improve the suffix tree by adding a leaf information array to the middle node, thus avoiding the traversal of the algorithm to the subtree. 2) A new type of approximate tandem repeats, evolutionary tandem repeats, is introduced. Because the previous algorithms can not solve the problem of searching evolutionary tandem repeats, a search algorithm based on hamming distance is proposed. For a given length of repetition unit, the time complexity of this algorithm is Oan ln2n 2, which solves the problem of searching evolutionary tandem repeats. In order to illustrate the correctness and validity of the algorithm, this paper applies these two methods to the actual genomic DNA sequences. The results show that the LZ decomposition based tandem repeat finding method can find more tandem repeats. The search method based on hamming distance solves the problem of searching evolutionary tandem repeats.
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2009
【分類號】：R346

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張德彰;翟滇;;現(xiàn)場DNA生物檢材的提取及注意事項(xiàng)[J];云南警官學(xué)院學(xué)報(bào);2011年03期

2 梁小虎;唐煥文;劉林華;;環(huán)境毒物對聚腺苷二磷酸核糖聚合酶表達(dá)影響[J];中國職業(yè)醫(yī)學(xué);2011年03期

3 劉杰;陶健;;抗腫瘤藥物的現(xiàn)狀及發(fā)展趨勢[J];科技致富向?qū)?2011年23期

4 范晶;;聚丙烯酰胺凝膠中DNA銀染色檢測方法的改進(jìn)及其效果比較[J];中國醫(yī)藥導(dǎo)報(bào);2011年19期

5 孔敏敏;李艷華;董宇輝;王文雅;袁其朋;;大腸桿菌DNA復(fù)制相關(guān)蛋白PriC的初步研究[J];中醫(yī)學(xué)報(bào);2011年06期

6 安群星;李翠瑩;陳蕤;陳曉鵬;穆士杰;;人類血小板抗原基因分型參考品的制備及鑒定[J];中國輸血雜志;2011年05期

7 吳蓉;張隆;華玲;戴俊華;劉麗麗;康向東;;尿液中大腸埃希菌實(shí)時(shí)熒光定量聚合酶鏈反應(yīng)檢測方法的建立[J];檢驗(yàn)醫(yī)學(xué);2011年06期

8 劉煒;張瓊梅;;巖白菜素與DNA相互作用的光譜研究[J];海南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年02期

9 賈立永;鄭磊;干寧;王前;;基于碳納米管修飾的無酶型新型甲胎蛋白安培免疫傳感器研究[J];熱帶醫(yī)學(xué)雜志;2011年05期

10 高蘇亞;范濤;楊莉?qū)?王黎;李華;;姜黃素-Fe~(2+)穩(wěn)定常數(shù)的測定及其與鮭魚精DNA的相互作用研究[J];分析試驗(yàn)室;2011年08期

相關(guān)會(huì)議論文 前10條

1 劉海英;陳剛;步宇翔;;堿基對的多銅修飾對DNA導(dǎo)電性的增強(qiáng)作用[A];中國化學(xué)會(huì)第28屆學(xué)術(shù)年會(huì)第13分會(huì)場摘要集[C];2012年

2 趙宏遠(yuǎn);李俊杰;桑潤滋;;單細(xì)胞凝膠電泳技術(shù)檢測不同處理山羊精子DNA損傷[A];中國畜牧獸醫(yī)學(xué)會(huì)動(dòng)物繁殖學(xué)分會(huì)第十五屆學(xué)術(shù)研討會(huì)論文集（下冊）[C];2010年

3 劉玲;付強(qiáng);朱化彬;彭秀麗;郝海生;杜衛(wèi)華;趙學(xué)明;王棟;;牛毛囊基因組DNA制備方法的比較研究[A];中國畜牧獸醫(yī)學(xué)會(huì)動(dòng)物繁殖學(xué)分會(huì)第十五屆學(xué)術(shù)研討會(huì)論文集（上冊）[C];2010年

4 梁春柳;;一個(gè)新的篩選化合物與DNA交互作用的簡便方法[A];2010年全國藥物毒理學(xué)學(xué)術(shù)會(huì)議論文集[C];2010年

5 張文眾;李永寧;方瑾;梁春來;張倩男;;體外新評價(jià)方法——完整細(xì)胞核DNA檢測板[A];全國生化/工業(yè)與衛(wèi)生毒理學(xué)學(xué)術(shù)會(huì)議論文集[C];2010年

6 鄒丹丹;汪海林;;基于DNA甲基化結(jié)合蛋白MBD的甲基化分析[A];中國化學(xué)會(huì)第28屆學(xué)術(shù)年會(huì)第2分會(huì)場摘要集[C];2012年

7 張曄;杜智;楊斌;高英堂;;檢測外周血中游離DNA的應(yīng)用前景(綜述)[A];天津市生物醫(yī)學(xué)工程學(xué)會(huì)第29屆學(xué)術(shù)年會(huì)暨首屆生物醫(yī)學(xué)工程前沿科學(xué)研討會(huì)論文集[C];2009年

8 趙淑珍;劉光珍;;DNA免疫吸附治療狼瘡性腎炎的臨床觀察[A];第十一屆全國中西醫(yī)結(jié)合腎臟病學(xué)術(shù)會(huì)議論文匯編[C];2010年

9 陳士林;;中藥DNA條形碼鑒定體系[A];第十屆全國藥用植物及植物藥學(xué)術(shù)研討會(huì)論文摘要集[C];2011年

10 陸佳飛;周克隆;王縵;;磁珠法快速提取乙型肝炎病毒DNA的研究及其在診斷試劑中的應(yīng)用[A];第五次全國免疫診斷暨疫苗學(xué)術(shù)研討會(huì)論文匯編[C];2011年

相關(guān)重要報(bào)紙文章 前10條

1 記者 李含;“DNA之父”詹姆斯·沃森做客清華論壇[N];新清華;2008年

2 ;英國：含冤入獄27年,DNA助他洗脫罪名[N];新華每日電訊;2009年

3 李志暉 秦亞洲 曹國廠;我國大規(guī)模利用DNA技術(shù)“打拐”[N];中國改革報(bào);2009年

4 本報(bào)駐特拉維夫記者 陳克勤;DNA偽造帶來的震動(dòng)[N];光明日報(bào);2009年

5 本報(bào)記者 張巍巍;DNA樣本也能作假[N];科技日報(bào);2009年

6 記者 鄭曉春;可區(qū)分真?zhèn)蜠NA的檢測技術(shù)問世[N];科技日報(bào);2009年

7 沈建民;企業(yè)公民DNA從何而來[N];21世紀(jì)經(jīng)濟(jì)報(bào)道;2009年

8 記者 魏萍;做DNA鑒定不用去外地[N];寧夏日報(bào);2010年

9 日報(bào)記者 曾繁華　閆友明 通訊員 劉曉穎;DNA：我的應(yīng)用很廣泛[N];柳州日報(bào);2010年

10 韋崇結(jié) 劉曉穎;DNA，讓作惡之徒現(xiàn)原形[N];廣西政協(xié)報(bào);2010年

相關(guān)博士學(xué)位論文 前10條

1 郭曉蘭;端粒功能異常誘導(dǎo)的DNA損傷反應(yīng)及其在腫瘤發(fā)生中的作用與分子機(jī)制[D];重慶醫(yī)科大學(xué);2010年

2 陳志健;1.8 GHz微波對X射線和阿霉素致淋巴細(xì)胞DNA損傷修復(fù)及對蛋白表達(dá)的影響[D];浙江大學(xué);2010年

3 朱慧芳;Y家族DNA聚合酶對化學(xué)致癌物MNNG應(yīng)答的轉(zhuǎn)錄調(diào)控研究[D];浙江大學(xué);2009年

4 萬超;抗豬瘟嵌合DNA疫苗及TRIF的DNA疫苗佐劑效應(yīng)研究[D];武漢大學(xué);2009年

5 孫曉南;融合多肽靶向DNA蛋白激酶自主磷酸化的放射增敏實(shí)驗(yàn)研究[D];浙江大學(xué);2011年

6 趙麗霞;克隆綿羊印記相關(guān)基因的DNA甲基化研究[D];內(nèi)蒙古農(nóng)業(yè)大學(xué);2010年

7 沈美龍;基于DNA免疫的乙型肝炎病毒表面抗原大中小蛋白的免疫原性研究[D];南京醫(yī)科大學(xué);2010年

8 徐鐵剛;細(xì)菌DNA磷硫�；揎椗c限制[D];上海交通大學(xué);2008年

9 高鵬;特異性介導(dǎo)DNA轉(zhuǎn)導(dǎo)的多結(jié)構(gòu)域嵌合蛋白的構(gòu)建、表達(dá)及鑒定[D];吉林大學(xué);2011年

10 康大偉;DNA分子器件場效應(yīng)理論研究[D];山東大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 李芳;基于磁性微粒的法醫(yī)樣本DNA純化[D];西北大學(xué);2011年

2 黎君;1，2-二氯乙烷對人外周血淋巴細(xì)胞DNA損傷的人群調(diào)查和實(shí)驗(yàn)室研究及神經(jīng)行為功能測試研究[D];浙江大學(xué);2011年

3 蘆麗淦;柚皮素及聚乙二醇增強(qiáng)乙肝DNA疫苗免疫效果的研究[D];河南大學(xué);2010年

4 楊錦艷;六種香豆素有效成分與DNA相互作用的研究[D];山西醫(yī)科大學(xué);2010年

5 林啟凰;用于乳腺蛋白標(biāo)志基因檢測的DNA電化學(xué)生物傳感器的研究[D];福建醫(yī)科大學(xué);2010年

6 于文靜;亞麻韌皮部特異啟動(dòng)子克隆與26份種質(zhì)DNA指紋圖譜構(gòu)建[D];中國農(nóng)業(yè)科學(xué)院;2010年

7 Rebecca Simisola Agboola;硼（B）和氯化鈉脅迫處理誘導(dǎo)高粱（Sorghum bicolor）自交系發(fā)生形態(tài)和DNA甲基化的變異[D];東北師范大學(xué);2010年

8 石微;溴氰菊酯致大鼠DNA損傷及損傷后修復(fù)功能的影響[D];青島大學(xué);2010年

9 張諾;DNA-納米羥基磷灰石修飾電極的制備及在生物分析中的應(yīng)用[D];濟(jì)南大學(xué);2010年

10 郭珈辰;基于圖形表示的DNA相似性分析及進(jìn)化樹構(gòu)建算法研究[D];湖南大學(xué);2010年

，

本文編號：1905426