An efficient algorithm for supertrees |
| |
| Authors: | Mariana Constantinescu David Sankoff |
| |
| Affiliation: | (1) Present address: Départment d'Informatique, Université de Moncton, E1A 3E9 Moncton, (Nouveau Brunswick), Canada;(2) Present address: Centre de Recherches Mathématiques, Université de Montréal, C. P., Succ. A, H3C 3J7 Montréal, (Quebec), Canada |
| |
| Abstract: | Givenk rooted binary treesA1, A2, ..., Ak, with labeled leaves, we generateC, a unique system of lineage constraints on common ancestors. We then present an algorithm for constructing the set of rooted binary treesB, compatible with all ofA1, A2, ..., Ak. The running time to obtain one such supertree isO(k2 n2), wheren is the number of distinct leaves in all of the treesA1, A2, ..., Ak. |
| |
| Keywords: | Tree compatibility Constraints on trees Supertrees Consensus trees |
| 本文献已被 SpringerLink 等数据库收录！ |
|
