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

对理解宿主/寄生虫系统的一个重要贡献是同源性的重建，即。例如，寄生虫和宿主的遗传图谱相互映射，以及相关进化事件的识别和（相对）定年：宿主和寄生虫的物种形成以及通过宿主偏好的变化获得和损失寄生虫。在自然界中，多个寄生虫物种感染同一宿主，而相同的寄生虫影响一系列宿主物种，这是规则而不是例外。多宿主/多寄生虫系统的进化不仅具有学术意义，而且对控制传染病具有潜在的影响。具有有效水平转移机制的移动的遗传元件（例如逆转录病毒和质粒）的进化是另一个应用领域。然而，数学模型和计算工具，到目前为止，几乎完全集中在单个寄生虫与单个主机和多个寄生虫与一个主机的关联。在这里，我们建议缩小这一差距，并制定一个正式的框架，以及计算工具来研究co-prolifergenies，描述多主机，多寄生虫组合。为此，我们将扩展到和解寄生虫和宿主树之间的关系的和解图的概念，开发合适的评分计划，这样的广义模型，并探讨主机/寄生虫系统及其密切相关的基因/物种系统的算法方法的推广。结合宿主/寄生虫协会和洪水的基因组数据的数据迅速增加的身体，我们设想，能够治疗多对多协会的新一代工具将提供新的见解紧密相连的进化机制，共同进化的集合也超出了宿主/寄生虫系统的范围。

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.