Optimization Online


The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences

Stephen J Maher (maher***at***zib.de)
John M Murray (j.murray***at***unsw.edu.au)

Abstract: This paper presents a novel application of operations research techniques to the analysis of HIV env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying the key features of env involves two steps: first, calculating the covariance of amino acid combinations and positions to form a network of related and compensatory mutations; and second, developing an integer program to identify the smallest completely connected subgraph of the constructed covariance network. The integer program developed for this analysis, labelled the unrooted set covering connected subgraph problem (USCCSP), integrates a set covering problem and connectivity evaluation, the latter formulated as a network flow problem. The resulting integer program is very large and complex, requiring the use of Benders' decomposition to develop an efficient solution approach. The results will demonstrate the necessity of applying acceleration techniques to the Benders' decomposition solution approach and the effectiveness of these techniques for solving the USCCSP.

Keywords: OR in medicine, HIV env sequence, Benders' decomposition, acceleration techniques

Category 1: Applications -- Science and Engineering (Biomedical Applications )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Zuse Institute Berlin, Berlin, Germany and University of New South Wales, Sydney, Australia. June 2014.

Download: [PDF]

Entry Submitted: 06/06/2014
Entry Accepted: 06/06/2014
Entry Last Modified: 06/06/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society