Algorithms for Reconstructing Evolutionary Relationships between Phylogenies: The Multi-Valued Case

对理解宿主/寄生虫系统的一个重要贡献是共同发育的重建，即寄生虫和宿主系统发育的相互映射，以及相关进化事件的鉴定和（相对）定年：宿主和寄生虫的物种形成以及通过宿主偏好的变化获得和失去寄生虫。在自然界中，多种寄生虫感染同一宿主是一种规律而非例外，而同一种寄生虫又影响一系列宿主物种。多宿主/多寄生虫系统的进化不仅具有学术意义，而且对传染病的管理也有潜在的影响。具有有效水平转移机制的移动遗传元件的进化，如逆转录病毒和质粒是另一个应用领域。然而，迄今为止，数学模型和计算工具几乎完全集中在单个寄生虫与单个宿主以及多个寄生虫与单个宿主的关联上。在这里，我们建议缩小这一差距，并开发一个正式的框架以及计算工具来研究描述多宿主，多寄生虫组合的共系统发育。为此，我们将把已经得到充分研究的和解图概念扩展到寄生虫和宿主树之间的和解关系，为这种广义模型开发合适的评分方案，并探索宿主/寄生虫系统及其密切相关的基因/物种系统的算法方法的泛化。结合宿主/寄生虫关联的快速增长的数据体和大量的基因组数据，我们设想能够处理多对多关联的新一代工具将为紧密联系、共同进化的组合的进化机制提供新的见解，这些机制也超出了宿主/寄生虫系统的范围。

An important contribution towards understanding host/parasite systems is the reconstruction of cophylogenies, i. e., the mapping of parasite and host phylogenies onto each other and the identification and (relative) dating of the pertinent evolutionary events: speciation of host and parasites as well as gain and loss of parasites through changes in host preferences. In nature, it is the rule rather than the exception that multiple parasite species infect the same host, while the same parasites affects a range of host species. The evolution of multi-host/multi-parasite systems is not only of academic interest but also has potential consequences for managing infectious diseases. The evolution of mobile genetic elements with efficient mechanisms for horizontal transfer, such as retroviruses and plasmids is another field of application. Nevertheless, mathematical models and computational tools so far have focused nearly exclusively on associations of single parasites with single hosts and multiple parasites with a single host. Here we propose to close this gap and develop a formal framework as well as computational tools to study co-phylogenies that describe multi-host, multi-parasite assemblages. To this end, we will extend the well-studied concept of reconciliation maps to reconciliation relations between parasite and host trees, develop suitable scoring schemes for such generalized models, and explore generalizations of the algorithmic approaches for host/parasite systems and their closely related gene/species systems. In conjunction with a rapidly increasing body of data on host/parasite associations and the deluge of genomic data, we envision that a new generation of tools capable of treating many-to-many associations will provide new insights into the evolutionary mechanisms of tightly linked, co-evolving assemblages also beyond the scope of host/parasite systems.