Discrete optimization for some TSP-like genome mapping problems

David Mester, Y. Ronin, M. Korostishevsky, Z. Frenkel, Olli Bräysy, W. Dullaert, B Raa, A. Korol

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review

Abstract

Several problems in modern genome mapping analysis belong to the field of discrete optimization on a set of all possible orders. In this paper we propose formulations, mathematical models and algorithms for genetic/genomic mapping problem, that can be formulated in TSP-like terms. These include: ordering of marker loci (or genes) in multilocus genetic mapping (MGM), multilocus consensus mapping (MCGM), and physical mapping problem (PMP). All these problems are considered as computationally challenging because of noisy marker scores, large-size data sets, specific constraints on certain classes of orders, and other complications. The presence of specific constrains on ordering of some elements in these problems does not allow applying effectively the well-known powerful discrete optimization algorithms like Cutting-plane, Genetic algorithm with EAX crossover and famous Lin-Kernighan. In the paper we demonstrate that developed by us Guided Evolution Strategy algorithms successfully solves this class of discrete constrained optimization problems. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on three genetic/genomic problems with up to 2,500 points.

Original languageEnglish
Title of host publicationHandbook of Optimization Theory: Decision Analysis and Application
PublisherNova Science Publishers, Inc.
Pages1-39
Number of pages39
ISBN (Print)9781608765003
Publication statusPublished - Jan 2011

Fingerprint

Discrete Optimization
Genome
Genomics
Cutting Planes
Evolution Strategies
Constrained Optimization Problem
Complications
Crossover
Locus
Optimization Algorithm
Genetic Algorithm
Mathematical Model
Gene
Formulation
Term
Demonstrate

Cite this

Mester, D., Ronin, Y., Korostishevsky, M., Frenkel, Z., Bräysy, O., Dullaert, W., ... Korol, A. (2011). Discrete optimization for some TSP-like genome mapping problems. In Handbook of Optimization Theory: Decision Analysis and Application (pp. 1-39). Nova Science Publishers, Inc..
Mester, David ; Ronin, Y. ; Korostishevsky, M. ; Frenkel, Z. ; Bräysy, Olli ; Dullaert, W. ; Raa, B ; Korol, A. / Discrete optimization for some TSP-like genome mapping problems. Handbook of Optimization Theory: Decision Analysis and Application. Nova Science Publishers, Inc., 2011. pp. 1-39
@inbook{434808b2eab54f5f9e277795878a23b1,
title = "Discrete optimization for some TSP-like genome mapping problems",
abstract = "Several problems in modern genome mapping analysis belong to the field of discrete optimization on a set of all possible orders. In this paper we propose formulations, mathematical models and algorithms for genetic/genomic mapping problem, that can be formulated in TSP-like terms. These include: ordering of marker loci (or genes) in multilocus genetic mapping (MGM), multilocus consensus mapping (MCGM), and physical mapping problem (PMP). All these problems are considered as computationally challenging because of noisy marker scores, large-size data sets, specific constraints on certain classes of orders, and other complications. The presence of specific constrains on ordering of some elements in these problems does not allow applying effectively the well-known powerful discrete optimization algorithms like Cutting-plane, Genetic algorithm with EAX crossover and famous Lin-Kernighan. In the paper we demonstrate that developed by us Guided Evolution Strategy algorithms successfully solves this class of discrete constrained optimization problems. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on three genetic/genomic problems with up to 2,500 points.",
author = "David Mester and Y. Ronin and M. Korostishevsky and Z. Frenkel and Olli Br{\"a}ysy and W. Dullaert and B Raa and A. Korol",
year = "2011",
month = "1",
language = "English",
isbn = "9781608765003",
pages = "1--39",
booktitle = "Handbook of Optimization Theory: Decision Analysis and Application",
publisher = "Nova Science Publishers, Inc.",

}

Mester, D, Ronin, Y, Korostishevsky, M, Frenkel, Z, Bräysy, O, Dullaert, W, Raa, B & Korol, A 2011, Discrete optimization for some TSP-like genome mapping problems. in Handbook of Optimization Theory: Decision Analysis and Application. Nova Science Publishers, Inc., pp. 1-39.

Discrete optimization for some TSP-like genome mapping problems. / Mester, David; Ronin, Y.; Korostishevsky, M.; Frenkel, Z.; Bräysy, Olli; Dullaert, W.; Raa, B; Korol, A.

Handbook of Optimization Theory: Decision Analysis and Application. Nova Science Publishers, Inc., 2011. p. 1-39.

Research output: Chapter in Book / Report / Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - Discrete optimization for some TSP-like genome mapping problems

AU - Mester, David

AU - Ronin, Y.

AU - Korostishevsky, M.

AU - Frenkel, Z.

AU - Bräysy, Olli

AU - Dullaert, W.

AU - Raa, B

AU - Korol, A.

PY - 2011/1

Y1 - 2011/1

N2 - Several problems in modern genome mapping analysis belong to the field of discrete optimization on a set of all possible orders. In this paper we propose formulations, mathematical models and algorithms for genetic/genomic mapping problem, that can be formulated in TSP-like terms. These include: ordering of marker loci (or genes) in multilocus genetic mapping (MGM), multilocus consensus mapping (MCGM), and physical mapping problem (PMP). All these problems are considered as computationally challenging because of noisy marker scores, large-size data sets, specific constraints on certain classes of orders, and other complications. The presence of specific constrains on ordering of some elements in these problems does not allow applying effectively the well-known powerful discrete optimization algorithms like Cutting-plane, Genetic algorithm with EAX crossover and famous Lin-Kernighan. In the paper we demonstrate that developed by us Guided Evolution Strategy algorithms successfully solves this class of discrete constrained optimization problems. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on three genetic/genomic problems with up to 2,500 points.

AB - Several problems in modern genome mapping analysis belong to the field of discrete optimization on a set of all possible orders. In this paper we propose formulations, mathematical models and algorithms for genetic/genomic mapping problem, that can be formulated in TSP-like terms. These include: ordering of marker loci (or genes) in multilocus genetic mapping (MGM), multilocus consensus mapping (MCGM), and physical mapping problem (PMP). All these problems are considered as computationally challenging because of noisy marker scores, large-size data sets, specific constraints on certain classes of orders, and other complications. The presence of specific constrains on ordering of some elements in these problems does not allow applying effectively the well-known powerful discrete optimization algorithms like Cutting-plane, Genetic algorithm with EAX crossover and famous Lin-Kernighan. In the paper we demonstrate that developed by us Guided Evolution Strategy algorithms successfully solves this class of discrete constrained optimization problems. The efficiency of the proposed algorithm is demonstrated on standard TSP problems and on three genetic/genomic problems with up to 2,500 points.

UR - http://www.scopus.com/inward/record.url?scp=84897332116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84897332116&partnerID=8YFLogxK

M3 - Chapter

SN - 9781608765003

SP - 1

EP - 39

BT - Handbook of Optimization Theory: Decision Analysis and Application

PB - Nova Science Publishers, Inc.

ER -

Mester D, Ronin Y, Korostishevsky M, Frenkel Z, Bräysy O, Dullaert W et al. Discrete optimization for some TSP-like genome mapping problems. In Handbook of Optimization Theory: Decision Analysis and Application. Nova Science Publishers, Inc. 2011. p. 1-39