Geodesic
Least resolved trees for two-colored best match graphs
Journal of graph algorithms and applications, Tome 25 (2021) no. 1, pp. 397-416 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

In phylogenetic combinatorics, 2-colored best match graphs (2-BMGs) form a subclass of sink-free bi-transitive digraphs that describe the most closely related genes between a pair of species in an evolutionary scenario. They are explained by a unique least resolved tree (LRT). In this paper, the concept of support vertices is introduced and used to derive an $O(|V|+|E|\log^2|V|)$-time algorithm that recognizes a 2-BMG and constructs its LRT. The approach can be extended to allow the recognition of binary-explainable 2-BMGs with the same complexity. An empirical comparison emphasizes the efficiency of the new algorithm.
DOI : 10.7155/jgaa.00564
Keywords: best matches, least resolved trees, recognition algorithm, polynomial-time algorithm 
@article{JGAA_2021_25_1_a17,
     author = {David Schaller and Manuela Gei{\ss} and Marc Hellmuth and Peter Stadler},
     title = {Least resolved trees for two-colored best match graphs},
     journal = {Journal of graph algorithms and applications},
     pages = {397--416},
     year = {2021},
     volume = {25},
     number = {1},
     doi = {10.7155/jgaa.00564},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00564/}
}
TY  - JOUR
AU  - David Schaller
AU  - Manuela Geiß
AU  - Marc Hellmuth
AU  - Peter Stadler
TI  - Least resolved trees for two-colored best match graphs
JO  - Journal of graph algorithms and applications
PY  - 2021
SP  - 397
EP  - 416
VL  - 25
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00564/
DO  - 10.7155/jgaa.00564
LA  - en
ID  - JGAA_2021_25_1_a17
ER  - 
%0 Journal Article
%A David Schaller
%A Manuela Geiß
%A Marc Hellmuth
%A Peter Stadler
%T Least resolved trees for two-colored best match graphs
%J Journal of graph algorithms and applications
%D 2021
%P 397-416
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00564/
%R 10.7155/jgaa.00564
%G en
%F JGAA_2021_25_1_a17
David Schaller; Manuela Geiß; Marc Hellmuth; Peter Stadler. Least resolved trees for two-colored best match graphs. Journal of graph algorithms and applications, Tome 25 (2021) no. 1, pp. 397-416. doi: 10.7155/jgaa.00564

Cité par Sources :