Gene Maps Linearization Using Genomic Rearrangement Distances

Constructing consensus genetic maps in comparative analysis

The construction of consensus genetic maps is a very challenging problem in computational biology. Many computational approaches have been proposed on the basis of only the marker order relations provided by a given set of individual genetic maps. In this article, we propose a comparative approach to constructing consensus genetic maps for a genome, which further takes into account the order relations from a closely related genome when resolving ordering conflicts among individual genetic maps. It aims to retain as many order relations as possible from individual genetic maps while achieving the minimum rearrangement distance to the reference genome. We implement the proposed approach as an integer linear program and test it on both simulated and real biological datasets. The experimental results show that it is capable of constructing more accurate consensus genetic maps than the most recent approach called MergeMap.

Genetic map refinement using a comparative genomic approach

Following various genetic mapping techniques conducted on different segregating populations, one or more genetic maps are obtained for a given species. However, recombination analyzes and other methods for gene mapping often fail to resolve the ordering of some pairs of neighboring markers, thereby leading to sets of markers ambiguously mapped to the same position. Each individual map is thus a partial order defined on the set of markers, and can be represented as a Directed Acyclic Graph (DAG). In this article, given a phylogenetic tree with a set of DAGs labeling each leaf (species), the goal is to infer, at each leaf, a single combined DAG that is as resolved as possible, considering the complementary information provided by individual maps, and the phylogenetic information provided by the species tree. After combining the individual maps of a leaf into a single DAG, we order incomparable markers by using two successive heuristics for minimizing two distances on the species tree: the breakpoint distance, and the Kemeny distance. We apply our algorithms to the plant species represented in the Gramene database, and we evaluate the simplified maps we obtained.

An approximation algorithm for the minimum breakpoint linearization problem

In the recent years, there has been a growing interest in inferring the total order of genes or markers on a chromosome, since current genetic mapping efforts might only suffice to produce a partial order. Many interesting optimization problems were thus formulated in the framework of genome rearrangement. As an important one among them, the minimum breakpoint linearization (MBL) problem is to find the total order of a partially ordered genome that minimizes its breakpoint distance to a reference genome whose genes are already totally ordered. It was previously shown to be NP-hard, and the algorithms proposed so far are all heuristic. In this paper, we present an {m(2)+m/2}-approximation algorithm for the MBL problem, where m is the number of gene maps that are combined together to form a partial order of the genome under investigation.