Abstrakt. I evolutionär biologi, en karaktär är en funktion χ från en uppsättning X av nuvarande arter till en ändlig uppsättning tillstånd. Antag att arten i X har utvecklats enligt ett bifurkerande träd T. Biologer skulle vilja använda tecken för att härleda detta träd. Anta att χ är resultatet av en evolutionär process på T som inte har inneburit omvända eller parallella övergångar, sådana tecken kallas homoplasy-fri. I detta fall ger χ direkt kombinatorisk information om det underliggande evolutionära trädet T för X. Vi överväger frågan om hur många homoplasy-fria tecken som krävs för att T ska kunna rekonstrueras korrekt. Vi etablerar först lägre gränser som visar att, när antalet stater begränsas, antalet homoplasy-fria tecken som krävs för att rekonstruera T växer (åtminstone) linjärt med storleken på X. Däremot visar vårt huvudresultat att när tillståndsutrymmet är tillräckligt stort kan varje bifurkerande träd unikt bestämmas av bara fem homoplasyfria karaktärer. Vi beskriver kortfattat relevansen av detta resultat för några nya typer av genomiska data, och för sammanslagningen av evolutionära träd.
REF visade att en uppsättning med 3 tecken inte är tillräcklig för att definiera ett träd, men en uppsättning med 5 tecken är.
Tree Reconstruction From Multi-State Characters
{'venue': 'Advances in Applied Mathematics 28', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}