Transmembrane Helix Assembly by Max-Min Ant System Algorithm

Because of the rapid progress in biochemical and structural studies of membrane proteins, considerable attention has been given on developing efficient computational methods for solving low-to-medium resolution structures using sparse structural data. In this study, we demonstrate a novel algorithm, max-min ant system (MMAS), designed to find an assembly of α-helical transmembrane proteins using a rigid helix arrangement guided by distance constraints. The new algorithm generates a large variety with finite number of orientations of transmembrane helix bundle and finds the solution that is matched with the provided distance constraints based on the behavior of ants to search for the shortest possible path between their nest and the food source. To demonstrate the efficiency of the novel search algorithm, MMAS is applied to determine the transmembrane packing of KcsA and MscL ion channels from a limited distance information extracted from the crystal structures, and the packing of KvAP voltage sensor domain using a set of 10 experimentally determined constraints, and the results are compared with those of two popular used stochastic methods, simulated annealing Monte Carlo method and genetic algorithm.