Figure 1

Sequence graph. graphA and graphB, each containing an alternative path due to indels in a previous alignment (A), are aligned with a variant of the Needleman-Wunsch algorithm [10] (B), which selects homologous paths during backtracking (thick arrows). Double lines indicate matched nodes (start and end nodes are always matched). In our example the selected homologous paths indicate that the additional edge in graphA is a deletion and the "T" in graphB is an insertion. For new indels (unmatched nodes along the homologous path) new edges are added to the graph representing the ambiguity, that these new indels might be either insertions or deletions. Finally, the graphs are merged according to the homologies defined by the alignment (C). The paths through graphsAB represent the possible ancestral sequences in which unused paths (dotted) are annotated with a penalty score and are less likely to be reused in subsequent alignments.