ILP-WGD-Reconstructor

A Unified ILP Framework for Core Ancestral Genome Reconstruction Problems

One of the key computational problems in comparative genomics is the reconstruction of genomes of ancestral species based on genomes of extant species. Since most dramatic changes in genomic architectures are caused by genome rearrangements, this problem is often posed as minimization of the number of genome rearrangements between extant and ancestral genomes. The basic case of three given genomes is known as the genome median problem. Whole genome duplications (WGDs) represent yet another type of dramatic evolutionary events and inspire the reconstruction of pre-duplicated ancestral genomes, referred to as the genome halving problem.

ILP-WGD-Reconstructor contains polynomial-size integer linear programming (ILP) formulations for the aforementioned problems. Moreover, it can also produce ILP formulations for the restricted and conserved versions of the median and halving problems, which combine the advantages of homology- and rearrangements-based methods. The full list of ILP formulations is the following:

• Genome Median Problem (GMP)
• Intermediate Genome Median Problem (IGMP)
• Conserved Genome Median Problem (CGMP)
• Double Distance Problem (DDP)
• Guided Genome Halving Problem (GGHP)
• Restricted Guided Genome Halving Problem (RGGHP)
• Conserved Guided Genome Halving Problem (CGGHP)

Dependencies

ILP-WGD-Reconstructor requires third-party tool installations:

• The Gurobi Optimizer software.
  Instructions on how to install the Gurobi Optimizer can be found here. The Gurobi Optimizer has a free academic license.
• The Gurobi Python Interface
• Networkx Python library
• Breakpoint Graph library

Usage

Refer to usage guide for each ILP formulation:

• Genome Median Problem
• Intermediate Genome Median Problem
• Conserved Genome Median Problem
• Double Distance Problem
• Guided Genome Halving Problem
• Restricted Guided Genome Halving Problem
• Conserved Guided Genome Halving Problem

Publications

P. Avdeyev, N. Alexeev, Y. Rong, and M. A. Alekseyev. "A Unified ILP Framework for Core Ancestral Genome Reconstruction Problems". (submitted)

P. Avdeyev, N. Alexeev, Y. Rong, and M. A. Alekseyev. "A Unified ILP Framework for Genome Median, Halving, and Aliquoting Problems under DCJ". Lecture Notes in Computer Science, 2017.

Authors

• Pavel Avdeyev
• Nikita Alexeev
• Yongwu Rong
• Max A. Alekseyev

Contacts

Please report any issues directly to the github issue tracker. Also, you can send your feedback to [email protected]