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 |
