Complexity of modification problems for reciprocal best match graphs

DOI10.1016/J.TCS.2019.12.033MaRDI QIDQ2290642zbMATH OpenOpenAlexWikidataFDO

Authors Marc Hellmuth, Manuela Geiß, Peter F. Stadler

Publication date 29 January 2020

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

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

zbMATH Keywords

NP-hardnessparameterized algorithmseditingorthology relationbicluster graphhierarchically colored cographsreciprocal best matches

Mathematics Subject Classification ID

Applications of graph theory (05C90) Genetics and epigenetics (92D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08)

Abstract: Reciprocal best match graphs (RBMGs) are vertex colored graphs whose vertices represent genes and the colors the species where the genes reside. Edges identify pairs of genes that are most closely related with respect to an underlying evolutionary tree. In practical applications this tree is unknown and the edges of the RBMGs are inferred by quantifying sequence similarity. Due to noise in the data, these empirically determined graphs in general violate the condition of being a ``biologically feasible RBMG. Therefore, it is of practical interest in computational biology to correct the initial estimate. Here we consider deletion (remove at most $k$ edges) and editing (add or delete at most $k$ edges) problems. We show that the decision version of the deletion and editing problem to obtain RBMGs from vertex colored graphs is NP-hard. Using known results for the so-called bicluster editing, we show that the RBMG editing problem for $2$-colored graphs is fixed-parameter tractable. A restricted class of RBMGs appears in the context of orthology detection. These are cographs with a specific type of vertex coloring known as hierarchical coloring. We show that the decision problem of modifying a vertex-colored graph (either by edge-deletion or editing) into an RBMG with cograph structure or, equivalently, to an hierarchically colored cograph is NP-complete.

Recommendations

• Complexity of modification problems for best match graphs
• Reciprocal best match graphs
• Best match graphs and reconciliation of gene trees with species trees
• The structure of 2-colored best match graphs
• Best match graphs

Cites work

• Applying modular decomposition to parameterized cluster editing problems
• Approximating Clique and Biclique Problems
• Best match graphs
• Biclustering in data mining
• Biclustering via sparse singular value decomposition
• Biclustering with heterogeneous variance
• Complement reducible graphs
• Complexity and parameterized algorithms for cograph editing
• Correlation Clustering and Biclustering With Locally Bounded Errors
• Exact algorithms for cluster editing: Evaluation and experiments
• Fast biclustering by dual parameterization
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Hybrid metaheuristic for bicluster editing problem
• Improved Algorithms for Bicluster Editing
• Improved biclustering of microarray data demonstrated through systematic performance tests
• New heuristics for the bicluster editing problem
• On bipartite and multipartite clique problems
• Orthology relations, symbolic ultrametrics, and cographs
• Recognizing P₄ -Sparse Graphs in Linear Time
• Some perfect coloring properties of graphs
• The maximum edge biclique problem is NP-complete

Cited in

(5)

• Complete characterization of incorrect orthology assignments in best match graphs
• Indirect identification of horizontal gene transfer
• Forbidden configurations and dominating bicliques in undirected 2-quasi best match graphs
• Reciprocal best match graphs
• Complexity of modification problems for best match graphs

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

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