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

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

0.00 Avg rating0 Votes
Article ID: iaor201527856
Volume: 248
Issue: 2
Start Page Number: 668
End Page Number: 680
Publication Date: Jan 2016
Journal: European Journal of Operational Research
Authors: ,
Keywords: sets, health services, graphs, programming: integer
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 connected subgraph of the constructed covariance network that exhibits a set covering property. 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 and heuristic approaches for solving the USCCSP.

Reviews

Required fields are marked *. Your email address will not be published.