Robinson-Foulds (RF) avstånd är det överlägset mest använda måttet på olikhet mellan träd. Även om fördelningen av dessa avstånd har undersökts i 20 år, en algoritm som är explicit polynom tid har ännu inte beskrivits för att beräkna fördelningen för träd runt ett givet träd. I den här artikeln härleder vi en polynom-tidsalgoritm för denna distribution. Vi visar hur fördelningen kan approximeras genom en Poissonfördelning som bestäms av andelen blad som ligger i "körsbär" av det givna trädet. Vi beskriver också hur våra resultat kan användas för att härleda normaliseringskonstanter som krävs i en nyligen föreslagen maximal sannolikhet strategi för superträd konstruktion. Ç T REE jämförelsemått används ofta i fylogenetik för att jämföra evolutionära träd [3], [9] och utföra statistiska tester-till exempel, för att testa om två träd är mer "betydande olika" från varandra än man kan förvänta sig om ett eller båda träd slumpvis valdes [6], [7]. För att ta itu med dessa statistiska frågor måste man bestämma fördelningen av mätvärdet enligt någon nullmodell (se t.ex. [6], [7] ). Den symmetriska skillnaden eller Robinson-Foulds metrisk är det mest använda måttet på skillnader mellan fylogenetiska träd, och dess fördelning är särskilt attraktiv att studera. I ett viktigt dokument [4] beskrev författarna denna fördelning av träd i förhållande till ett fast referensträd via ett system för att generera funktioner. Detta gjorde det möjligt för författarna att beräkna fördelningen explicit för små träd och gav ett verktyg för analytiska resultat på denna fördelning i senare arbete av andra. Det tillvägagångssätt som beskrivs i [4] verkar dock inte omedelbart tillhandahålla en polynom-tidsalgoritm för beräkning av denna fördelning, och för större träd kan deras tillvägagångssätt vara beräkningsmässigt oöverkomligt. I denna uppsats beskriver vi hur man beräknar fördelningen av Robinson-Foulds metrisk i förhållande till ett fast träd. Vi visar också hur fördelningen kan approximeras av en Poisson distribution vars parameter beror på bara en aspekt av trädform-antalet "körsbär". Vår undersökning av fördelningen av metriska har också motiverats av dess relevans för en ny metod för "superträd" konstruktion som bygger på maximal sannolikhet [12]. I synnerhet, vår algoritm tillåter normaliseringskonstanterna i sannolikhetsberäkningarna att beräknas explicit. Vi beskriver hur dessa normalisering konstanter beror svagt på aspekter av formen på trädet-till exempel, hur många "körsbär" trädet har. Vi börjar med att påminna om en viss terminologi.
Dessutom kan fördelningen av Robinson-Foulds avstånd i förhållande till ett fast träd beräknas i linjär tid REF.
Computing the Distribution of a Tree Metric
{'venue': 'IEEE/ACM Transactions on Computational Biology and Bioinformatics', 'journal': 'IEEE/ACM Transactions on Computational Biology and Bioinformatics', 'mag_field_of_study': ['Medicine', 'Mathematics', 'Biology']}