Generalized tree alignment
   HOME

TheInfoList



OR:

In computational
phylogenetics In biology, phylogenetics (; from Greek φυλή/ φῦλον [] "tribe, clan, race", and wikt:γενετικός, γενετικός [] "origin, source, birth") is the study of the evolutionary history and relationships among or within groups ...
, generalized tree alignment is the problem of producing a
multiple sequence alignment Multiple sequence alignment (MSA) may refer to the process or the result of sequence alignment of three or more biological sequences, generally protein, DNA, or RNA. In many cases, the input set of query sequences are assumed to have an evolutio ...
and a phylogenetic tree on a set of sequences simultaneously, as opposed to separately. Formally, Generalized tree alignment is the following optimization problem. Input: A set S and an edit distance function d between sequences, Output: A tree T leaf-labeled by S and labeled with sequences at the internal nodes, such that \Sigma_ d(e) is minimized, where d(e) is the edit distance between the endpoints of e. Note that this is in contrast to tree alignment, where the tree is provided as input.


References

Computational phylogenetics {{Bioinformatics-stub