Biomedical subjects

D I Mester

Publications and source records attributed to D I Mester.

3 recordsLinked to original sources

PubMed2005

Multilocus consensus genetic maps (MCGM): formulation, algorithms, and results.

In process of creating genetic maps different labs/research groups obtain overlapping parts of the map. Merging these parts into one integrative map is based on looking for maximum shared marker orders among the maps. Really, not all shared markers of such maps have consensus order that obstructs building of the integrative maps. In this paper we propose a new approach to build verified multilocus consensus genetic maps in which shared markers always are integrated in stable consensus order. The approach is based on combined analysis of initial mapping data rather than manipulating with previously constructed maps. We show that more effective and reliable solutions may be obtained based on "synchronized ordering" facilitated by cycles of "re-sampling-->ordering-->removing unstable markers". The proposed formulation of consensus genetic mapping can be considered as a version of traveling salesperson problem (TSP) that we refer to as synchronized-TSP. From the viewpoint of optimization, synchronized-TSP belongs to discrete constrained optimization problems. Earlier we developed new powerful and fast guided evolution strategy algorithms for some types of discrete constrained optimization. These algorithms were used here as a basis for solving more challenging problems of consensual marker ordering.

Algorithms↗

PubMed2004

Fast and high precision algorithms for optimization in large-scale genomic problems.

There are several very difficult problems related to genetic or genomic analysis that belong to the field of discrete optimization in a set of all possible orders. With n elements (points, markers, clones, sequences, etc.), the number of all possible orders is n!/2 and only one of these is considered to be the true order. A classical formulation of a similar mathematical problem is the well-known traveling salesperson problem model (TSP). Genetic analogues of this problem include: ordering in multilocus genetic mapping, evolutionary tree reconstruction, building physical maps (contig assembling for overlapping clones and radiation hybrid mapping), and others. A novel, fast and reliable hybrid algorithm based on evolution strategy and guided local search discrete optimization was developed for TSP formulation of the multilocus mapping problems. High performance and high precision of the employed algorithm named guided evolution strategy (GES) allows verification of the obtained multilocus orders based on different computing-intensive approaches (e.g., bootstrap or jackknife) for detection and removing unreliable marker loci, hence, stabilizing the resulting paths. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on simulated data of multilocus genetic maps up to 1000 points per linkage group.

Algorithms↗

PubMed2003

Efficient multipoint mapping: making use of dominant repulsion-phase markers.

The paper is devoted to the problem of multipoint gene ordering with a particular focus on "dominance" complication that acts differently in conditions of coupling-phase and repulsion-phase markers. To solve the problem we split the dataset into two complementary subsets each containing shared codominant markers and dominant markers in the coupling-phase only. Multilocus ordering in the proposed algorithm is based on pairwise recombination frequencies and using the well-known travelling salesman problem (TSP) formalization. To obtain accurate results, we developed a multiphase algorithm that includes synchronized-marker ordering of two subsets assisted by re-sampling-based map verification, combining the resulting maps into an integrated map followed by verification of the integrated map. A new synchronized Evolution-Strategy discrete optimization algorithm was developed here for the proposed multilocus ordering approach in which common codominant markers facilitate stabilization of the marker order of the two complementary maps. High performance of the employed algorithm allows systematic treatment for the problem of verification of the obtained multilocus orders, based on computing-intensive bootstrap and jackknife technologies for detection and removing unreliable marker scores. The efficiency of the proposed algorithm was demonstrated on simulated and real data.

Algorithms↗