Efficient implied alignment

Abstract

Background: Given a binary tree [Formula: see text] of n leaves, each leaf labeled by a string of length at most k, and a binary string alignment function ⊗, an implied alignment can be generated to describe the alignment of a dynamic homology for [Formula: see text]. This is done by first decorating each node of [Formula: see text] with an alignment context using ⊗, in a post-order traversal, then, during a subsequent pre-order traversal, inferring on which edges insertion and deletion events occurred using those internal node decorations.

Results: Previous descriptions of the implied alignment algorithm suggest a technique of "back-propagation" with time complexity [Formula: see text]. Here we describe an implied alignment algorithm with complexity [Formula: see text]. For well-behaved data, such as molecular sequences, the runtime approaches the best-case complexity of Ω(k∗n).

Conclusions: The reduction in the time complexity of the algorithm dramatically improves both its utility in generating multiple sequence alignments and its heuristic utility.

Keywords: Dynamic homology; Implied alignment; Multiple string alignment; Phylogenetics; Sequence alignment; Tree alignment.

Fig. 1

Example pre-order alignment for a parent node and it’s left child

Fig. 2

Best case pre-order runtime

Fig. 3

Worst case pre-order runtime

Fig. 4

Fungi pre-order runtime

Fig. 5

Metazoa pre-order runtime