A character table is consistent if there exists a binary treeT whose splits does not conflict
with the characters encoded in the table.
Recall that the characters in a character table are represented in array notation,
where A[i]=1 if the i-th taxon possesses the character and A[i]=0 otherwise.
Given this notation, we can easily convert the character to its split notation.
Recall also that given a binary tree T, the removal of an edge e divides T into two disconnectedsubtrees. In particular, the taxa have been divided into a split S2∣Sc2, which
can be used to label e.
We then say that a character table is consistent if there is a binary tree T whose edge
splits do not conflict with the splits deriving from the table's characters. Two
splits S1∣Sc1 and S2∣Sc2 conflict when
all four intersectionsS1∩S2, S1∩Sc2, Sc1∩S2, and
Sc1∩Sc2 are nonempty.
As a simple example, consider the conflicting quartets{a,b}∣{c,d} and {a,c}∣{b,d},
which correspond to distinct trees on the taxa a, b, c, and d.
Report a typo
Page:
Context:
Flag as inappropriate
Are you sure you want to flag this comment as inappropriate?
Welcome to Rosalind!
Rosalind is a platform for learning bioinformatics through problem solving.
Please login with Google/Twitter/Facebook or
register a new account.