Improved Hidden Markov Model training for multiple sequence alignment by a particle swarm optimization-evolutionary algorithm hybrid

Multiple sequence alignment (MSA) is one of the basic problems in computational biology. Realistic problem instances of MSA are computationally intractable for exact algorithms. One way to tackle MSA is to use Hidden Markov Models (HMMs), which are known to be very powerful in the related problem domain of speech recognition. However, the training of HMMs is computationally hard and there is no known exact method that can guarantee optimal training within reasonable computing time. Perhaps the most powerful training method is the Baum-Welch algorithm, which is fast, but bears the problem of stagnation at local optima. In the study reported in this paper, we used a hybrid algorithm combining particle swarm optimization with evolutionary algorithms to train HMMs for the alignment of protein sequences. Our experiments show that our approach yields better alignments for a set of benchmark protein sequences than the most commonly applied HMM training methods, such as Baum-Welch and Simulated Annealing.     

Emergent properties in the behaviour of a virtual spider robot

Using a virtual spider robot, we studied hypotheses about the weaving behaviour of orb spiders. Our model spiders built virtual webs that mimicked perfectly the visual architecture of real webs of the garden cross spider Araneus diadematus. The matching of capture spiral and auxiliary spiral pitch was an apparently emergent property in both types of web. This validated our interpretation of the garden spider''s web-building decision rules, which use strictly local interactions with previously placed threads to generate global architecture.     

A virtual robot to model the use of regenerated legs in a web-building spider

The garden cross orb-spider, Araneus diadematus, shows behavioural responses to leg loss and regeneration that are reflected in the geometry of the web's capture spiral. We created a virtual spider robot that mimicked the web construction behaviour of thus handicapped real spiders. We used this approach to test the correctness and consistency of hypotheses about orb web construction. The behaviour of our virtual robot was implemented in a rule-based system supervising behaviour patterns that communicated with the robot's sensors and motors. By building the typical web of a nonhandicapped spider our first model failed and led to new observations on real spiders. We realized that in addition to leg position, leg posture could also be of importance. The implementation of this new hypothesis greatly improved the results of our simulation of a handicapped spider. Now simulated webs, like the real webs of handicapped spiders, had significantly more gaps in successive spiral turns compared with webs of nonhandicapped spiders. Moreover, webs built by the improved virtual spiders intercepted prey as well as the digitized real webs. However, the main factors that affected web interception frequency were prey size, size of capture area and individual variance; having a regenerated leg, surprisingly, was relatively unimportant for this trait. Copyright 1999 The Association for the Study of Animal Behaviour.