Exemplar or matching: modeling DCJ problems with unequal content genome data

DOI10.1007/S10878-015-9940-4MaRDI QIDQ346504zbMATH OpenOpenAlexFDO

Authors Zhaoming Yin, Jijun Tang, Stephen W. Schaeffer, David A. Bader

Publication date 29 November 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

genome rearrangementLin-Kernighan heuristicdouble-cut and join (DCJ)

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Abstract: The edit distance under the DCJ model can be computed in linear time for genomes with equal content or with Indels. But it becomes NP-Hard in the presence of duplications, a problem largely unsolved especially when Indels are considered. In this paper, we compare two mainstream methods to deal with duplications and associate them with Indels: one by deletion, namely DCJ-Indel-Exemplar distance; versus the other by gene matching, namely DCJ-Indel-Matching distance. We design branch-and-bound algorithms with set of optimization methods to compute exact distances for both. Furthermore, median problems are discussed in alignment with both of these distance methods, which are to find a median genome that minimizes distances between itself and three given genomes. Lin-Kernighan (LK) heuristic is leveraged and powered up by sub-graph decomposition and search space reduction technologies to handle median computation. A wide range of experiments are conducted on synthetic data sets and real data sets to show pros and cons of these two distance metrics per se, as well as putting them in the median computation scenario.

Recommendations

• A Lin-Kernighan heuristic for the DCJ median problem of genomes with unequal contents
• A fast and exact algorithm for the exemplar breakpoint distance
• On the DCJ Median Problem
• A linear time approximation algorithm for the DCJ distance for genomes with bounded number of duplicates
• Computing the rearrangement distance of natural genomes

Cites work

• scientific article; zbMATH DE number 1830749 (Why is no real title available?)
• Erratum: ``The approximability of the exemplar breakpoint distance problem
• Genomes Containing Duplicates Are Hard to Compare
• On the Approximability of Comparing Genomes with Duplicates
• Research in Computational Molecular Biology
• Sorting by Transpositions
• Steps toward accurate reconstructions of phylogenies from gene-order data.
• The reversal median problem
• Vector-valued wavelets with triangular support for method of moments applications

Cited in

(5)

• A linear algorithm for restructuring a graph
• A fast and exact algorithm for the exemplar breakpoint distance
• Bridging disparate views on the DCJ-indel model for a capping-free solution to the natural distance problem
• Linear algorithm for a cyclic graph transformation
• A Lin-Kernighan heuristic for the DCJ median problem of genomes with unequal contents

Describes a project that uses

Uses Software

• GASTS

This page was built for publication: Exemplar or matching: modeling DCJ problems with unequal content genome data

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