Tree construction using gaps

Gap blocks can be viewed as binary state characters: each event partitions the tree into two groups, the sequences with the gap and the sequences without the gap. Each event tells us which sequences belong into the same subtree, because when several sequences have the same gap, we know that the indel event happened in an ancestor of those sequences. In addition, it is not very likely that two equal indel events happen at exactly the same place of same length, therefore we ignore this case. We can use indel events to reconstruct the tree or at least parts of the tree. We want to build a minimum parsimony tree [7,8,9], i.e. minimum number of errors according to gap blocks. Gaps have been used before to reconstruct trees [24], but this has never been stated explicitly. We give a practical approach on how to use gaps for tree construction.
Example 4.1:  The MSA in Figure has four gap blocks. We use those blocks to partition the sequences (see Table ). Event 1 partitions the tree into the sequences $\{A, B\}$ and $\{C, D, E\}$. Events 2 and 4 do not add any information. Event 3 completes the tree (see Figure ).

  

Figure: Partitioning of sequences using gaps. The indel events are depicted in the tree.

Event     1         2        3         4
A: RPCVCP___VLRQAAQ__QVLQRQIIQGPQQLRRLF_AA
B: RPCACP___VLRQVVQ__QALQRQIIQGPQQLRRLF_AA
C: KPCVCPRQLVLRQAAHLAQQLYQGQ____RQVRRAF_VA
D: KPCVCPRQLVLRQAAH__QQLYQGQ____RQVRRLF_AA
E: KPCLCPKQAAVKQAAH__QQLYQGQLQGPKQVRRAFRLL

Event	Seqs with gaps	Seqs w/o gaps
1	{A, B}	{C, D, E}
2	{A, B, D, E}	{C}
3	{C, D}	{A, B, E}
4	{A, B, C, D}	{E}

To reconstruct a binary tree with n leaves completely, we need n-3 different partitions, where each partition must contain at least two elements (two leaves), because an indel in just one sequence does not supply any information.

  

Figure: Tree constructed using all four events. On the left is an unrooted version, on the right a rooted version of the same tree.