Simple test for prefect phylogeny
• | Fact: there exits perfect phylogeny if and only if and only if all pairs of characters are compatible | |
• | Special case: if we assume directed parsimony (0→1 only) then characters are compatible if and only if there do not exist tree taxa containing combinations (1,0),(0,1),(1,1) | |
• | Observe the last one is equivalent to non-overlapping criterion | |
• | Optimal algorithm: Gusfield O(nm): n = # taxa; m= #characters |