生物信息导论英文论文practicalsuffixtreeconstruction生物信息导论英文论文-practicalsuffixtreeconstruction

《生物信息导论英文论文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