| Autor: |
Geiß, Manuela, Chavez, Edgar, Gonzalez, Marcos, Lopez, Alitzel, Stadler, Bärbel M. R., Valdivia, Dulce I., Hellmuth, Marc, Rosales, Maribel H., Stadler, Peter F. |
| Rok vydání: |
2018 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1007/s00285-019-01332-9 |
| Popis: |
THIS IS A CORRECTED VERSION INCLUDING AN APPENDED CORRIGENDUM. Best match graphs arise naturally as the first processing intermediate in algorithms for orthology detection. Let $T$ be a phylogenetic (gene) tree $T$ and $\sigma$ an assignment of leaves of $T$ to species. The best match graph $(G,\sigma)$ is a digraph that contains an arc from $x$ to $y$ if the genes $x$ and $y$ reside in different species and $y$ is one of possibly many (evolutionary) closest relatives of $x$ compared to all other genes contained in the species $\sigma(y)$. Here, we characterize best match graphs and show that it can be decided in cubic time and quadratic space whether $(G,\sigma)$ derived from a tree in this manner. If the answer is affirmative, there is a unique least resolved tree that explains $(G,\sigma)$, which can also be constructed in cubic time. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
