资源描述：
《reconstructing phylogenies with memetic algorithms and branch-and-bound》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ReconstructingPhylogenieswithMemeticAlgorithmsandBranch-and-BoundJos¶eE.Gallardo,CarlosCottaAntonioJ.Fern¶andezDept.LenguajesyCienciasdelaComputaci¶on,ETSIInform¶atica,UniversityofM¶alaga,CampusdeTeatinos,29071-M¶alaga,Spain.E-mail:fpepeg,ccottap,afdezg@lcc.uma.esAbstractAphylogen
2、etictreerepresentstheevolutionaryhistoryforacollectionoforganisms.Weconsidertheproblemofinferringsuchatreegivenacertainsetofdata(genomic,proteomic,orevenmorphological).Giventhecomputationalhardnessofthisproblem,exactapproachesareinherentlylimited.However,exacttechniquescanstillbeu
3、sefultoendowheuristicapproacheswithproblem-awareness.Weanalyzethishybridizationinthecontextofmemeticalgorithmsandbranch-and-boundtechniques.Focusingintheultrametricmodelforphylogeneticinference,weshowthatthiscombinationcanbesynergetic.Weanalyzetheparametersinvolvedinthishybridmode
4、l,anddeterminearobustsettingforthese.Asummaryofrelatedworkisalsoprovided.1IntroductionPhylogenetictreesprovideahierarchicalrepresentationofthedegreeofclosenessamongasetoforganisms.Thereconstructionofphylogenetictreesfromdataisundoubtedlyataskofparamountimportanceinmolecularbiology
5、.Ithasdirectimplicationsinareassuchasmultiplesequencealignment[20],proteinstructureprediction[53]ormolecularepidemiologicalstudiesofviruses[48],justtociteafew.Unfortunately,thistaskturnsouttobeveryhardfromthecomputationalpointofview.Firstofall,thephylogenyproblemisintrinsicallycom
6、plex:NP-hardnesshasbeenshownforphylogeneticinferenceunderseveralmodels[11,12,13,17,62].Secondly,whiletheutilizationofaqualitymeasureforevaluatinghierarchiesimpliesthede¯nitionofanoptimizationproblem,itsglobaloptimumhasnotthesamesigni¯canceasinotherclassicalproblems:theexistenceofs
7、omeuncertaintyintheunderlyingempiricaldatamaymakehigh-qualitysuboptimalsolutionsbeequallyvalid.Duetothereasonsjustmentioned,theuseofclassicalexacttechniquescanbeconsideredgenerallyinappropriateinthiscontext.Indeed,theuseofheuristictechniquesinthisdomainseemsmuchmoreadequate.Thesec
8、anrangefromsimpleconstructiveheur
