Processing math: 100%

Glossary

Consistent character table

A character table is consistent if there exists a binary tree T 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 disconnected subtrees. In particular, the taxa have been divided into a split S2Sc2, 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 S1Sc1 and S2Sc2 conflict when all four intersections S1S2, S1Sc2, Sc1S2, and Sc1Sc2 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.

Welcome to Rosalind!

Rosalind is a platform for learning bioinformatics through problem solving.
Please login with Google/Twitter/Facebook or register a new account.