PI-1552: Protein Threading: From Mathematical Models to Parallel
Implementations
Rumen Andonov, Stefan Balev, Nicola Yanev
http://www.irisa.fr/bibli/publi/pi/2003/1552/1552.html
ftp://ftp.irisa.fr/techreports/2003/PI-1552.ps.gz
22 pages - septembre 2003

Abstract
This paper presents a new network flow formulation for the problem of
protein 3D structure prediction by threading. Several integer
programming models based on this formulation are proposed and compared.
Their properties allow efficient decomposition and application of
parallel branch-and-cut algorithm significantly reducing the running
time. The efficiency of our approaches is confirmed by extensive
computational experiments.

Résumé
Le problème de reconnaissance de repliement de protéines connu sous le
nom de protein threading problem est considéré dans cet article comme un
modèle de réseau de flot. Dans ce modèle nous proposons et comparons
plusieurs formulations MIP (Mixed-Integer Programming). Leurs propriétés
permettent de découper le problème en sous-problèmes qui peuvent être
efficacement résolus par une méthode d'élagage branch-and-cut. Une
version parallèle de cette méthode est aussi proposée. L'efficacité de
notre approche est illustrée par des expériences numériques sur des
protéines de taille très importante.

Keywords: Protein Threading, Network Optimization, Integer Programming,
Linear Programming, Large Scale Problems, Parallel Algorithms

Mots clefs: Problème de reconnaissance de repliement de protéines,
programmation en nombres entiers, réseau de flot, CPLEX