TITLE

# DCA based algorithms for multiple sequence alignment (MSA)

AUTHOR(S)
Le Thi, Hoai; Pham Dinh, Tao; Belghiti, Moulay
PUB. DATE
September 2014
SOURCE
Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p501
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the multiple sequence alignment in its equivalent binary linear program, called 'Maximum Weight Trace' problem. This problem is beforehand recast as a polyhedral DC program with the help of exact penalty techniques in DC programming. Our customized DCA, requiring solution of a few linear programs, is original because it converges after finitely many iterations to a binary solution while it works in a continuous domain. To scale-up large-scale (MSA), a constraint generation technique is introduced in DCA. Preliminary computational experiments on benchmark data show the efficiency of the proposed algorithm DCAMSA, which generally outperforms some standard algorithms.
ACCESSION #
97029517

## Related Articles

• On degeneracy in linear programming and related problems. George, Karen; Osborae, M. R. // Annals of Operations Research;1993, Vol. 46/47 Issue 1-4, p343

Methods related to Wolfe's recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are...

• A regularized simplex method. Fábián, Csaba; Eretnek, Krisztián; Papp, Olga // Central European Journal of Operations Research;Dec2015, Vol. 23 Issue 4, p877

In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a polyhedral convex objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized...

• A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

• The Covering Tour Problem. Gendreau, Michel; Laporte, Gilbert; Semet, Frédéric // Operations Research;Jul/Aug97, Vol. 45 Issue 4, p568

The Covering Tour Problem (CTP) is defined on a graph G = (V âˆª W, E), where W is a set of vertices that must be covered. The CTP consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a prespecified distance from the cycle. The...

• CLUSTERING BASED POLYHEDRAL CONIC FUNCTIONS ALGORITHM IN CLASSIFICATION. OZTURK, GURKAN; CIFTCI, MEHMET TAHIR // Journal of Industrial & Management Optimization;Jul2015, Vol. 11 Issue 3, p921

In this study, a new algorithm based on polyhedral conic func tions (PCFs) is developed to solve multi-class supervised data classiffication problems. The k PCFs are constructed for each class in order to separate it from the rest of the data set. The k-means algorithm is applied to find...

• LP-BASED COMBINATORIAL PROBLEM SOLVING. Hoffman, K.; Padberg, M. // Annals of Operations Research;1985, Vol. 4 Issue 1-4, p145

A tutorial outline of the polyhedral theory that underlies linear programming (LP)-based combinatorial problem solving is given. Design aspects of a combinatorial problem solver are discussed in general terms. Three computational studies in combinatorial problem solving using the polyhedral...

• ON NONLINEAR FRACTIONAL PROGRAMMING. Dinkelbach, Werner // Management Science;Mar67, Vol. 13 Issue 7, p492

The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric...

• Global infimum of strictly convex quadratic functions with bounded perturbations. Hoang Xuan Phu; Vo Minh Pho // Mathematical Methods of Operations Research;Oct2010, Vol. 72 Issue 2, p327

The problem of minimizing $${\tilde f=f+p}$$ over some convex subset of a Euclidean space is investigated, where f( x) = x Ax + b x is strictly convex and | p| is only assumed to be bounded by some positive number s. It is shown that the function $${\tilde f}$$ is strictly outer ?-convex for any...

• Algorithms for the Frame of a Finitely Generated Unbounded Polyhedron. Dulá, José H.; López, Francisco J. // INFORMS Journal on Computing;Winter2006, Vol. 18 Issue 1, p97

Consider two finite sets A and V of points in m-dimensional space. The convex hull of A and the conical hull of V can be combined to create a finitely generated unbounded polyhedron. We explore the geometry of these polyhedral sets to design, implement, test, and compare two different algorithms...

Share