资源描述:
《生物信息导论论文.docx》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、PracticalSuffixTreeConstructionSandeepTataRichardA.HankinsJigneshM・PatelUniversityofMichiganAbstractLargestringdatasetsarecommoninanumberofemergingtextandbiologicaldatabaseapplications・Commonqueriesoversuchdatasetsincludebothexactandapproximatestringmatches.Thesequeriescanbeevaluatedveryef
2、ficientlybyusingasuffixtreeindexonthestringdataset.Althoughsuffixtreescanbeconstructedquicklyinmemoryforsmallinputdatasets,constructingpersistenttreesforlargedatasetshasbeenchallenging.Inthispaper,weexploresuffixtreeconstructionalgorithmsoverawidespectnimofdatasourcesandsizes・First,weshowt
3、hatonmodernprocessors,acache-efficientalgorithmwithO(n2)complexityoutperformsthepopularO(n)Ukkonenalgorithm,evenforin-memoryconstruction.Forlargerdatasets,thediskI/Orequirementquicklybecomesthebottleneckineachalgorithm'sperformance・Toaddressthisproblem,wepresentabuffermanagementstrategyfor
4、theO(/?2)algorithm,creatinganewdisk-basedconstructionalgorithmthatscalestosizesmuchlargerthanhavebeenpreviouslydescribedintheliterature・Ourapproachfaroutperformsthebestknowndiskbasedconstructionalgorithms.1IntroductionQueryinglargestringdatasetsisbecomingincreasinglyimportantinanumberofeme
5、rgingtextandlifesciencesapplications.Lifescienceresearchersareofteninterestedinexplorativequeryingoflargebiologicalsequencedatabases,suchasgenomesandlargesetsofproteinsequences・Manyofthesebiologicaldatasetsaregrowingatexponentialrates—forexample,thesizesofthesequencedatasetsinGenBankhavebe
6、endoublingeverysix-Pennissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeordistributedfordirectcommercialadvantage,theVLDBcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheVeryLargeDataBaseEndowment.T
7、ocopyotherwise,ortorepublish,requiresafeeand/orspecialpermissionfromtheEndowment.Proceedingsofthe30thVLDBConference,Toronto,Canada,2004teenmonths[31J.Consequently,methodsforefficientlyqueryinglargestringdatasetsarecriticaltothesuccessoftheseemergingdatabaseapp