作品校內選拔賽作品申報書作品校內選拔賽作品申報書作品校內選拔賽作品申報書作品校內選拔賽作品申報書編制僅供參考審核批準生效日期地址：電話：傳真:郵編:序號：編碼：第十一屆“挑戰杯”全國大學生課外學術科技作品競賽華南農業大學選拔賽作品申報書作品名稱：DNA壓縮及模式匹配研究平臺所在學院：信息學院申報者姓名（集體名稱）：劉少鵬類別：□自然科學類學術論文□哲學社會科學類社會調查報告和學術論文□科技發明制作A類□科技發明制作B類

說明1.申報者應在認真閱讀此說明各項內容后按要求詳細填寫。2．申報者在填寫申報作品情況時只需根據個人項目或集體項目填寫A1或A2表，根據作品類別（自然科學類學術論文、哲學社會科學類社會調查報告和學術論文、科技發明制作）分別填寫B1、B2或B3表。所有申報者可根據情況填寫C表。3．表內項目填寫時一律用打印，字跡要端正、清楚，此申報書可復制。4．序號、編碼由競賽組委會填寫。5．學術論文、社會調查報告及所附的有關材料必須是中文（若是外文，請附中文本），請用4號楷體打印在A4紙上，附于申報書后，字數在8000字以內,調查報告類每篇在15000字以內。6．其他參賽事宜請向校團委咨詢。聯系電話：，

A1．申報者情況（個人項目）說明：1．必須由申報者本人按要求填寫，申報者情況欄內必須填寫個人作品的第一作者（承擔申報作品60%以上的工作者）；2．本表中的學籍管理部門簽章視為對申報者情況的確認。申報者情況姓名劉少鵬性別男出生年月1984年9月所在學院信息學院專業計算機應用現學歷碩士年級二年級學制3年入學時間2007年9月作品全稱DNA壓縮及模式匹配研究平臺畢業論文題目通訊地址華南農業大學研究生宿舍6棟904郵政編碼510642單位電話常住地通訊地址廣東省潮州市潮安縣磷溪鎮溪口四村郵政編碼521000住宅電話093合作者情況姓名性別年齡學歷所在單位資格認定學院學籍管理部門意見□是□否若是，其學號為：19（學院蓋章）年月日院系負責人或導師意見本作品是否為課外學術科技或社會實踐活動成果。□是□否負責人簽名：年月日

B3．申報作品情況（科技發明制作）說明：1．必須由申報者本人填寫；2．3．本表必須附有研究報告，并提供圖表、曲線、試驗數據、原理結構圖、外觀圖（照片）,也可附鑒定證書和應用證書；4．作品分類請按照作品發明點或創新點所在類別填報。作品全稱DNA壓縮及模式匹配研究平臺作品分類（B）A．機械與控制（包括機械、儀器儀表、自動化控制、工程、交通、建筑等）B．信息技術（包括計算機、電信、通訊、電子等）C．數理（包括數學、物理、地球與空間科學等）D．生命科學（包括生物、農學、藥學、醫學、健康、衛生、食品等）E．能源化工（包括能源、材料、石油、化學、化工、生態、環保等）作品設計、發明的目的和基本思路，創新點，技術關鍵和主要技術指標目的二十世紀末生物信息學迅速發展，在信息的數量和質量上都極大的豐富了生物科學的數據資源，包括NCBI,EMBL,GDB等，DNA數據庫的數據量在以每年兩到三倍的數量增加。現在為存儲DNA數據需要越來越大的空間。因此，對DNA數據進行壓縮以減少存儲空間將是生物學家和計算機專家面臨的挑戰。由于DNA數據的特殊性，即DNA序列數據由A、C、G、T四個字母組成，并且DNA序列長度可達到上千萬個堿基對，使用傳統的數據壓縮算法并不理想。于是，必須研究專門針對DNA序列數據的壓縮算法：DNA壓縮算法。在生物學家對DNA序列數據的使用中，序列比對是生物信息學中最基本、最重要的操作之一。從實現的理論和技術上講，DNA序列比對的實質是一種特殊的模式匹配，而直接在壓縮后的DNA數據上進行序列比對其實質則是一種特殊的壓縮模式匹配，即DNA壓縮模式匹配。為了更好地研究DNA壓縮算法和DNA壓縮模式匹配算法，我們將建立一個研究平臺。該平臺主要用于管理和增加DNA壓縮算法和DNA壓縮模式匹配算法，存儲DNA序列數據、DNA壓縮數據，能實現各算法的效果的比較試驗，驗證算法的有效性。思路以Java技術和二次數據庫技術，建立一個不依賴具體機型和操作系統的DNA壓縮和DNA壓縮模式匹配研究的專用平臺；并利用該平臺，結合DNA序列數據的特點，研究DNA序列數據壓縮現有算法和提出新的算法，以有效減少DNA數據所占用的存儲空間；研究出專門針對DNA壓縮數據的壓縮模式匹配算法，以解決在不對DNA序列壓縮數據解壓或最小解壓縮的情況下實現序列比對功能。創新點1、可擴展利用面向對象的Java技術，建立專業的生物信息學研究平臺，可持續地開展DNA壓縮算法和DNA壓縮模式匹配算法的研究。具體地說，平臺的可擴展性體現在兩方面：一是有意義明確的包，尤其是包matching和compress。二是GUI界面都是用Swing組件寫成的，每個面板的功能都是相當明確，其中負責壓縮信息處理的CompressPanel和負責模式匹配的MatchingPanel就是很好的體現。假如，我們現在的平臺需要增加一個新的壓縮算法，那么我們要把這個壓縮算法設計為一個類，把它放到包compress中，再在面板CompressPanel中的樹狀選擇壓縮算法，為用戶增加一個新的選項，即可完成擴展。如果現在的平臺需要增加一個新的匹配算法，那么我們要把這個匹配算法設計為一個類，把它放到包matching中，再在面板MatchingPanel中的樹狀選擇匹配算法，為用戶增加一個新的選項，即可完成擴展。2、減少DNA序列存儲空間參考文本壓縮算法思想，根據DNA序列數據的特點，研究專門用于壓縮DNA序列數據的DNA壓縮算法。DNA壓縮算法可以高效地壓縮DNA序列數據，極大地減少DNA序列數據所占用的存儲空間。3、DNA序列比對研究利用壓縮模式匹配的思想，根據DNA序列數據的特點，專門研究在對DNA序列壓縮數據不解壓縮或最小解壓縮的情況下，直接在DNA壓縮數據庫中實現DNA序列比對的功能。4、直接使用壓縮DNA數據研究不是把DNA序列數據壓縮減小存儲空間作為唯一目標，而是把直接有效地利用DNA序列壓縮數據作為更重要的目標。技術關鍵1、面向對象的Java技術使得該平臺不依賴操作系統和具體機型，因此可運行在小型機、高級服務器、PC臺式機、筆記本電腦和Unix、Solaris、Windows和Linux等環境。2、多線程技術在java中，程序通過流控制來執行程序流，程序中單個順序的流控制稱為線程，多線程則指的是在單個程序中可以同時運行多個不同的線程，執行不同的任務。多線程意味著一個程序的多行語句可以看上去幾乎在同一時間內同時運行。3、Swing技術Swing組件被稱為輕量級組件（lightweightcomponent），是由純Javacode開發的，它不需要那些關于各種平臺的復雜的GUI功能，解決了Java因為窗口類而無法跨平臺的問題，并且不會占有太多的系統資源。Swing組件對比AWT組件具有更大強度的可移植性和靈活性。主要技術指標平臺可擴展性、算法效率、算法比較效果作品的科學性先進性（必須說明與現有技術相比、該作品是否具有突出的實質性技術特點和顯著進步。請提供技術性分析說明和參考文獻資料）1、采用java面向對象編程技術，具有良好的平臺無關性及功能可擴展性。2、研究DNA壓縮算法和DNA壓縮模式匹配算法具有重要意義，該平臺為研究人員的工作提供便捷。利用該平臺，作者已發表中文核心期刊文章一篇。3、目前針對DNA壓縮算法和DNA壓縮模式匹配算法的平臺不多。4、參考文獻很多，主要有DNA壓縮算法和DNA壓縮模式匹配算法等國內國外論文，請查閱。[1] DonAdjeroh,YongZhang,AmarMukherjee,MattPowell,TimBell,“DNASequenceCompressionUsingtheBurrows-WheelerTransform,”csb,,IEEEComputerSocietyBioinformaticsConference(CSB'02),2002[2] ChenX.,KwongLiM,“AcompressionalgorithmforDNAsequencesanditsapplicationsingenomecomparison”,InProceedings,10thWorkshoponGenomeInformatics(GIW’99),pp.52-61,1999.[4] BurrowsM.andWheeler.,“Ablock-sortinglosslessdatacompressionalgorithm”,TechnicalReport,DigitalEquipmentCorporation,PaloAlto,[5] TaoTao,AmarMukherjee,“PatternMatchinginLZWCompressedFiles,”IEEETransactionsonComputers,vol.54,no.8,pp.929-938,Aug.,2005.[6] T.Bell,M.Powell,A.Mukherjee,andD.Adjeroh,“SearchingBWTCompressedTextwiththeBoyer-MooreAlgorithmandBinarySearch”,Proc.DataCompressionConf.,pp.112-121,.[7] CHENLei,LUShiyong,RAMPatternMatchinginDNASequences:IEEEComputationalSystemsBioinformaticsConference,2004[C].Washington,[8] BOYERRS,MOOREJFastStringSearchingAlgorithm[J].CommunicationsoftheACM,1977,20(10):762–772.[9] Knuth,.,MorrisJr,.,Pratt,.:Fastpatternmatchinginstrings.SIAMJournalonComputing6,323–350(1977)[10] 張麗霞,張義青,林丕源,劉吉平．基于字符和0/1碼的DNA壓縮模式匹配算法．計算機應用研究,2007,24(9):22-24[11] 林毅申,林丕源.基于WebServices的生物信息解決方案[J].計算機應用研究,2005,22(6):157-158&164.[12] (英)著,羅靜初等譯.生物信息學概論.北京：北京大學出版社,作品在何時、何地、何種機構舉行的評審、鑒定、評比、展示等活動中獲獎及鑒定結果無。作品所處階段（）A實驗室階段B中試階段C生產階段D可初步應用，為算法研究提供一定的便利（自填）技術轉讓方式作品可展示的形式□實物、產品□模型□圖紙□磁盤□現場演示□圖片□錄像□樣品使用說明及該作品的技術特點和優勢，提供該作品的適應范圍、推廣前景的技術性說明、市場分析和經濟效益預測由于DNA數據庫的數據量在以每年兩到三倍的數量增加，因此將來使用壓縮的DNA數據會成為必然的趨勢，而要直接使用DNA壓縮數據，DNA壓縮模式匹配又是必須解決的問題。因此DNA壓縮和DNA壓縮模式匹配就有良好的應用前景。DNA壓縮算法及其DNA壓縮模式匹配算法的研究，有助于將DNA序列數據從較為高端的工作平臺(專用的存儲容量較大的服務器)遷移到更簡易的工作平臺(普通的存儲容量較小的計算機，如筆記本電腦或PDA)上，使得生物學家可以隨時隨地開展研究工作；DNA壓縮算法及其DNA壓縮模式匹配算法的研究，還可以為在普通工作平臺上建立專門的二級數據庫提供新的方法。專利申報情況□提出專利申報申報號申報日期年月日□已獲專利權批準批準號批準日期年月日□未提出專利申請科研管理部門簽章年月日

C.當前國內外同類課題研究水平概述說明：1.申報者可根據作品類別和情況填寫；2.填寫此欄有助于評審。為了對DNA數據進修壓縮，減小DNA數據所占用的空間，1993年GrumbachS.和TahiF.從經典的基于字典壓縮的LZ系列算法中提出BioCompress算法，從搜索和編碼兩方面針對DNA序列進行改進。1999年ChenX.,KwongS.和LiM.的GenCompress算法是對BioCompress算法的改進，使序列數據壓縮的速度和壓縮率提高到實用層次。2001年SatoH.,YoshiokaT.,KonagayaA.和ToyodaT.提出Cfect算法，引入后綴樹數據結構，提高搜索重復字符串速度，并提高序列數據的壓縮率。2002年，ChenX.,LiM.,MaB.和TrompJ.以生物數據序列比對為基礎，提出DNACompress算法，獲得了較高數據壓縮率。之后，計算機專家繼續不斷地努力，2005年Kordi,G.和Tabus,I.，ShengBao,ShiChen,ZhiqiangJing和RanRen，JieLiu,ShengBao,ZhiqiangJing和ShiChen均嘗試進一步改進算法，提高DNA數據的壓縮率。壓縮模式匹配(Compressedpatternmatching)思想于1992年由Amir和Benson首先提出，即給定文本T，根據某種壓縮算法進行壓縮得到壓縮串Z，給定模式串P，僅僅使用P和Z尋找P在T中的所有出現。不過，關于模式匹配算法的研究大多數只是針對普通的文本數據。因為DNA序列數據及其壓縮算法的特殊性，DNA壓縮模式匹配算法也需要進行專門研究，以具有更好的適應性。DNA壓縮模式匹配是生物信息學中一個新的研究領域，主要致力解決下面的問題：對給定的壓縮格式的DNA序列文件F和一個DNA模式P，在不解壓