Complexity of modification problems for best match graphs

DOI10.1016/J.TCS.2021.02.037MaRDI QIDQ2661779zbMATH OpenOpenAlexFDO

Authors David Schaller, Peter F. Stadler, Marc Hellmuth

Publication date 8 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.16909

zbMATH Keywords

best matchesforbidden subgraphsgraph modificationinteger linear programNP-hardnessrooted triples

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: Best match graphs (BMGs) are vertex-colored directed graphs that were introduced to model the relationships of genes (vertices) from different species (colors) given an underlying evolutionary tree that is assumed to be unknown. In real-life applications, BMGs are estimated from sequence similarity data. Measurement noise and approximation errors usually result in empirically determined graphs that in general violate characteristic properties of BMGs. The arc modification problems for BMGs aim at correcting such violations and thus provide a means to improve the initial estimates of best match data. We show here that the arc deletion, arc completion and arc editing problems for BMGs are NP-complete and that they can be formulated and solved as integer linear programs. To this end, we provide a novel characterization of BMGs in terms of triples (binary trees on three leaves) and a characterization of BMGs with two colors in terms of forbidden subgraphs.

Recommendations

• Complexity of modification problems for reciprocal best match graphs
• The structure of 2-colored best match graphs
• Quasi-best match graphs
• Best match graphs with binary trees
• Best match graphs

Cites work

• Algorithms on Strings, Trees and Sequences
• Best match graphs
• Best match graphs and reconciliation of gene trees with species trees
• Complete characterization of incorrect orthology assignments in best match graphs
• Complexity and parameterized algorithms for cograph editing
• Complexity classification of some edge modification problems
• Complexity of modification problems for reciprocal best match graphs
• Computing the Minimum Fill-In is NP-Complete
• Finding a maximum likelihood tree is hard
• Generating a random sink-free orientation in quadratic time
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Kernel and fast algorithm for dense triplet inconsistency
• New results on optimizing rooted triplets consistency
• Orthology relations, symbolic ultrametrics, and cographs
• Reciprocal best match graphs
• Reducibility among combinatorial problems
• The complexity of some edge deletion problems
• The graph menagerie: abstract algebra and the mad veterinarian
• Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time

Cited in

(11)

• Corrigendum to: ``Best match graphs
• Indirect identification of horizontal gene transfer
• Best match graphs with binary trees
• The structure of 2-colored best match graphs
• Complexity of modification problems for reciprocal best match graphs
• Quasi-best match graphs
• Least resolved trees for two-colored best match graphs
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
• Forbidden configurations and dominating bicliques in undirected 2-quasi best match graphs
• Automorphisms and quotients of 2-colored quasi best match graphs
• Inferring DAGs and phylogenetic networks from least common ancestors

This page was built for publication: Complexity of modification problems for best match graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2661779)