Bladmärkta träd används ofta för att beskriva evolutionära relationer, särskilt inom biologin. I denna miljö, yttre arter märka bladen av trädet, medan de inre hörn motsvarar anortal arter. Det finns olika tekniker för att rekonstruera dessa evolutionära träd från data, och ett viktigt problem är att avgöra hur "långt ifrån" två sådana rekonstruerade träd är från varandra, eller faktiskt från det sanna historiska trädet. För att undersöka denna fråga krävs trädmått, och dessa kan framkallas av operationer som omorganiserar träd lokalt. Här undersöker vi tre sådana operationer: närmaste grannbyte (NNI), underträdsprunge och regraft (SPR), och träd bisektion och återkoppling (TBR). Operationen SPR är av särskilt intresse eftersom den kan användas för att modellera biologiska processer såsom horisontell genöverföring och rekombination. Vi räknar antalet orotade binära träd en SPR från varje given orotade binära träd, samt ger nya övre och nedre gränser för diametern på adjacency grafen av träd under SPR och TBR. Vi visar också att problemet med att beräkna det minsta antalet TBR-åtgärder som krävs för att omvandla ett träd till ett annat kan reduceras till ett problem vars storlek är en funktion bara av avståndet mellan träden (och inte av storleken på de två träden), och därmed fastställa att problemet är fast-parameter dragbar.
Den vanligaste permutationsoperationen är Tree Bisektion och Reconnection (TBR) REF.
Subtree Transfer Operations and their Induced Metrics on Evolutionary Trees
{'venue': 'Annals of Combinatorics', 'journal': None, 'mag_field_of_study': ['Mathematics']}