Generalized tree alignment

In computational <a href="/facts/Phylogenetics/bw4rsovt">phylogenetics</a>, generalized tree alignment is the problem of producing a <a href="/facts/Multiple_sequence_alignment/en7c7SQs">multiple sequence alignment</a> and a <a href="/facts/Phylogenetic_tree/f5vVEpeY">phylogenetic tree</a> on a set of sequences simultaneously, as opposed to separately.
Formally, Generalized tree alignment is the following optimization problem.
Input: A set 
 
 
 
 S
 
 
 {\displaystyle S}
 
 and an edit distance function 
 
 
 
 d
 
 
 {\displaystyle d}
 
 between sequences,
Output: A tree 
 
 
 
 T
 
 
 {\displaystyle T}
 
 leaf-labeled by 
 
 
 
 S
 
 
 {\displaystyle S}
 
 and labeled with sequences at the internal nodes, such that 
 
 
 
 
 Σ
 
 e
 ∈
 T
 
 
 d
 (
 e
 )
 
 
 {\displaystyle \Sigma _{e\in T}d(e)}
 
 is minimized, where 
 
 
 
 d
 (
 e
 )
 
 
 {\displaystyle d(e)}
 
 is the edit distance between the endpoints of 
 
 
 
 e
 
 
 {\displaystyle e}
 
.
Note that this is in contrast to <a href="/facts/Tree_alignment/R8sRGmBB">tree alignment</a>, where the tree is provided as input.

Generalized tree alignment open-in-new

Generalized tree alignment