资源描述:
《生物信息导论英文论文practicalsuffixtreeconstruction生物信息导论英文论文-practicalsuffixtreeconstruction》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、PracticalSuffixTreeConstructionSandeepTataRichardA.HankinsJigneshM.PatelUniversityofMichigan24AbstractLargestringdatasetsarecommoninanumberofemergingtextandbiologicaldatabaseapplications.Commonqueriesoversuchdatasetsincludebothexactandapproximatestringmatches.The
2、sequeriescanbeevaluatedveryefficientlybyusingasuffixtreeindexonthestringdataset.Althoughsuffixtreescanbeconstructedquicklyinmemoryforsmallinputdatasets,constructingpersistenttreesforlargedatasetshasbeenchallenging.Inthispaper,weexploresuffixtreeconstructionalgori
3、thmsoverawidespectrumofdatasourcesandsizes.First,weshowthatonmodernprocessors,acache-efficientalgorithmwithO(n2)complexityoutperformsthepopularO(n)Ukkonenalgorithm,evenforin-memoryconstruction.Forlargerdatasets,thediskI/Orequirementquicklybecomesthebottleneckinea
4、chalgorithm’sperformance.Toaddressthisproblem,wepresentabuffermanagementstrategyfortheO(n2)algorithm,creatinganewdisk-basedconstructionalgorithmthatscalestosizesmuchlargerthanhavebeenpreviouslydescribedintheliterature.Ourapproachfaroutperformsthebestknowndiskbase
5、dconstructionalgorithms.1IntroductionQueryinglargestringdatasetsisbecomingincreasinglyimportantinanumberofemergingtextandlifesciencesapplications.Lifescienceresearchersareofteninterestedinexplorativequeryingoflargebiologicalsequencedatabases,suchasgenomesandlarge
6、setsofproteinsequences.Manyofthesebiologicaldatasetsaregrowingatexponentialrates—forexample,thesizesofthesequencedatasetsinGenBankhavebeendoublingeverysix-Permissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeordistributedfordir
7、ectcommercialadvantage,theVLDBcopyrightnoticeandthetitleofthepublicationanditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheVeryLargeDataBaseEndowment.Tocopyotherwise,ortorepublish,requiresafeeand/orspecialpermissionfromtheEndowment.Proceedingsofthe30t
8、hVLDBConference,Toronto,Canada,2004teenmonths[31].Consequently,methodsforefficientlyqueryinglargestringdatasetsarecriticaltothe24successoftheseemergingdatabase