DVDulce I. Valdivia

Dulce I. Valdivia

*This is an algorithmically generated author record based on publicly available information.

Dulce I. Valdivia has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Corrigendum to “Best match graphs”

    by David Schaller, Manuela Geiß, Edgar Chávez, Marcos González Laffitte, Alitzel López Sánchez, Bärbel M. R. Stadler, Dulce I. Valdivia, Marc Hellmuth, Maribel Hernández Rosales, Peter F. Stadler

    Two errors in the article Best Match Graphs (Geiß et al. in JMB 78: 2015–2057, 2019) are corrected. One concerns the tacit assumption that digraphs are sink-free, which has to be added as an additional precondition in Lemma 9, Lemma 11, Theorem 4. Correspondingly, Algorithm 2 requires that its input is sink-free. The second correction concerns an additional necessary condition in Theorem 9 required to characterize best match graphs. The amended results simplify the construction of least resolved trees for n-cBMGs, i.e., Algorithm 1. All other results remain unchanged and are correct as stated.


  • Open Access

    Best Match Graphs

    by Manuela Geiß, Edgar Chavez, Marcos Gonzalez, Alitzel Lopez, Bärbel M. R. Stadler, Dulce I. Valdivia, Marc Hellmuth, Maribel H. Rosales, Peter F. Stadler

    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.