A simulated annealing algorithm for finding consensus sequences

Motivation: A consensus sequence for a family of related sequences is, as the name suggests, a sequence that captures the features common to most members of the family. Consensus sequences are important in various DNA sequencing applications and are a convenient way to characterize a family of molecules. Results: This paper describes a new algorithm for finding a consensus sequence, using the popular optimization method known as simulated annealing. Unlike the conventional approach of finding a consensus sequence by first forming a multiple sequence alignment, this algorithm searches for a sequence that minimises the sum of pairwise distances to each of the input sequences. The resulting consensus sequence can then be used to induce a multiple sequence alignment. The time required by the algorithm scales linearly with the number of input sequences and quadratically with the length of the consensus sequence. We present results demonstrating the high quality of the consensus sequences and alignments produced by the new algorithm. For comparison, we also present similar results obtained using ClustalW. The new algorithm outperforms ClustalW in many cases.

A monolithic smoothing-gap algorithm for contact-impact based on the signed distance function

A new algorithm has been developed for smoothing the surfaces in finite element formulations of contact-impact. A key feature of this method is that the smoothing is done implicitly by constructing smooth signed distance functions for the bodies. These functions are then employed for the computation of the gap and other variables needed for implementation of contact-impact. The smoothed signed distance functions are constructed by a moving least-squares approximation with a polynomial basis. Results show that when nodes are placed on a surface, the surface can be reproduced with an error of about one per cent or less with either a quadratic or a linear basis. With a quadratic basis, the method exactly reproduces a circle or a sphere even for coarse meshes. Results are presented for contact problems involving the contact of circular bodies. Copyright (C) 2002 John Wiley Sons, Ltd.

Implementing the quantum random walk

Recently, several groups have investigated quantum analogues of random walk algorithms, both on a line and on a circle. It has been found that the quantum versions have markedly different features to the classical versions. Namely, the variance on the line, and the mixing time on the circle increase quadratically faster in the quantum versions as compared to the classical versions. Here, we propose a scheme to implement the quantum random walk on a line and on a circle in an ion trap quantum computer. With current ion trap technology, the number of steps that could be experimentally implemented will be relatively small. However, we show how the enhanced features of these walks could be observed experimentally. In the limit of strong decoherence, the quantum random walk tends to the classical random walk. By measuring the degree to which the walk remains quantum, '' this algorithm could serve as an important benchmarking protocol for ion trap quantum computers.

The impact of genotyping error on haplotype reconstruction and frequency estimation

The choice of genotyping families vs unrelated individuals is a critical factor in any large-scale linkage disequilibrium (LD) study. The use of unrelated individuals for such studies is promising, but in contrast to family designs, unrelated samples do not facilitate detection of genotyping errors, which have been shown to be of great importance for LD and linkage studies and may be even more important in genotyping collaborations across laboratories. Here we employ some of the most commonly-used analysis methods to examine the relative accuracy of haplotype estimation using families vs unrelateds in the presence of genotyping error. The results suggest that even slight amounts of genotyping error can significantly decrease haplotype frequency and reconstruction accuracy, that the ability to detect such errors in large families is essential when the number/complexity of haplotypes is high (low LD/common alleles). In contrast, in situations of low haplotype complexity (high LD and/or many rare alleles) unrelated individuals offer such a high degree of accuracy that there is little reason for less efficient family designs. Moreover, parent-child trios, which comprise the most popular family design and the most efficient in terms of the number of founder chromosomes per genotype but which contain little information for error detection, offer little or no gain over unrelated samples in nearly all cases, and thus do not seem a useful sampling compromise between unrelated individuals and large families. The implications of these results are discussed in the context of large-scale LD mapping projects such as the proposed genome-wide haplotype map.

Vision in the peafowl (Aves : Pavo cristatus)

The visual sense of the Indian blue-shouldered peafowl Pavo cristatus was investigated with respect to the spectral absorption characteristics of the retinal photoreceptors, the spectral transmittance of the ocular media and the topographic distribution of cells in the retinal ganglion cell layer. Microspectrophotometry revealed a single class of rod, four spectrally distinct types of single cone and a single class of double cone. In the case of the single cone types, which contained visual pigments with wavelengths of maximum absorbance (lambda(max)) at 424, 458, 505 and 567 nm, spectral filtering by the ocular media and the different cone oil droplets with which each visual pigment is associated gives predicted peak spectral sensitivities of 432, 477, 537 and 605 nm, respectively. Topographic analysis of retinal ganglion cell distribution revealed a large central area of increased cell density (at peak, 35,609 cells mm(-2)) with a poorly defined visual streak extending nasally. The peafowl has a calculated maximum spatial resolution (visual acuity) in the lateral visual field of 20.6 cycles degrees(-1). These properties of the peafowl eye are discussed with respect to its visual ecology and are compared with those of other closely related species.

Developmental changes in the cone visual pigments of black bream Acanthopagrus butcheri

The spectral absorption characteristics of the visual pigments in the photoreceptors of the black bream Acanthopagrus butcheri Munro (Sparidae, Teleostei), were measured using microspectrophotometry. A single cohort of fish aged 5-172 days post-hatch (dph), aquarium-reared adults and wild-caught juveniles were investigated. During the larval stage and in juveniles younger than 100 dph, two classes of visual pigment were found, with wavelengths of maximum absorbance (lambda(max)) at approximately 425 nm and 535 nm. Following double cone formation, from 40 dph onwards, the short wavelength-sensitive pigment was recorded in single cones and the longer wavelength-sensitive pigment in double cones. From 100 dph, a gradual shift in the lambda(max) towards longer wavelengths was observed in both cone types. By 160 dph, and in adults, all single cones had a lambda(max) at approximately 475 nm while the lambda(max) in double cones ranged from 545 to 575 nm. The relationships between the lambda(max) and the ratio of bandwidth:lambda(max), for changes in either chromophore or opsin, were modelled mathematically for the long-wavelength-sensitive visual pigments. Comparing our data with the models indicated that changes in lambda(max) were not mediated by a switch from an A(1) to A(2) chromophore, rather a change in opsin expression was most likely. The shifts in the lambda(max) of the visual pigments occur at a stage when the juvenile fish begin feeding in deeper, tannin-stained estuarine waters, which transmit predominantly longer wavelengths, so the spectral sensitivity changes may represent an adaptation by the fish to the changing light environment.

Application of the maximum entropy method to the (2 + 1)D four-fermion model

We investigate spectral functions extracted using the maximum entropy method from correlators measured in lattice simulations of the (2+1)-dimensional four-fermion model. This model is particularly interesting because it has both a chirally broken phase with a rich spectrum of mesonic bound states and a symmetric phase where there are only resonances. In the broken phase we study the elementary fermion, pion, sigma, and massive pseudoscalar meson; our results confirm the Goldstone nature of the π and permit an estimate of the meson binding energy. We have, however, seen no signal of σ→ππ decay as the chiral limit is approached. In the symmetric phase we observe a resonance of nonzero width in qualitative agreement with analytic expectations; in addition the ultraviolet behavior of the spectral functions is consistent with the large nonperturbative anomalous dimension for fermion composite operators expected in this model.

A subset-oriented algorithm for minimizing the number of steps required for synthesis of cyclic-peptide libraries

Libraries of cyclic peptides are being synthesized using combinatorial chemistry for high throughput screening in the drug discovery process. This paper describes the min_syn_steps.cpp program (available at http://www.imb.uq.edu.au/groups/smythe/tran), which after inputting a list of cyclic peptides to be synthesized, removes cyclic redundant sequences and calculates synthetic strategies which minimize the synthetic steps as well as the reagent requirements. The synthetic steps and reagent requirements could be minimized by finding common subsets within the sequences for block synthesis. Since a brute-force approach to search for optimum synthetic strategies is impractically large, a subset-orientated approach is utilized here to limit the size of the search. (C) 2002 Elsevier Science Ltd. All rights reserved.

Modelling High-Dimensional Data by Mixtures of Factor Analyzers

We focus on mixtures of factor analyzers from the perspective of a method for model-based density estimation from high-dimensional data, and hence for the clustering of such data. This approach enables a normal mixture model to be fitted to a sample of n data points of dimension p, where p is large relative to n. The number of free parameters is controlled through the dimension of the latent factor space. By working in this reduced space, it allows a model for each component-covariance matrix with complexity lying between that of the isotropic and full covariance structure models. We shall illustrate the use of mixtures of factor analyzers in a practical example that considers the clustering of cell lines on the basis of gene expressions from microarray experiments. (C) 2002 Elsevier Science B.V. All rights reserved.

Using siting algorithms in the design of marine reserve networks

Using benthic habitat data from the Florida Keys (USA), we demonstrate how siting algorithms can help identify potential networks of marine reserves that comprehensively represent target habitat types. We applied a flexible optimization tool-simulated annealing-to represent a fixed proportion of different marine habitat types within a geographic area. We investigated the relative influence of spatial information, planning-unit size, detail of habitat classification, and magnitude of the overall conservation goal on the resulting network scenarios. With this method, we were able to identify many adequate reserve systems that met the conservation goals, e.g., representing at least 20% of each conservation target (i.e., habitat type) while fulfilling the overall aim of minimizing the system area and perimeter. One of the most useful types of information provided by this siting algorithm comes from an irreplaceability analysis, which is a count of the number of, times unique planning units were included in reserve system scenarios. This analysis indicated that many different combinations of sites produced networks that met the conservation goals. While individual 1-km(2) areas were fairly interchangeable, the irreplaceability analysis highlighted larger areas within the planning region that were chosen consistently to meet the goals incorporated into the algorithm. Additionally, we found that reserve systems designed with a high degree of spatial clustering tended to have considerably less perimeter and larger overall areas in reserve-a configuration that may be preferable particularly for sociopolitical reasons. This exercise illustrates the value of using the simulated annealing algorithm to help site marine reserves: the approach makes efficient use of;available resources, can be used interactively by conservation decision makers, and offers biologically suitable alternative networks from which an effective system of marine reserves can be crafted.

An EM-based Semi-Parametric Mixture Model Approach to the Regression Analysis of Competing-Risks Data

We consider a mixture model approach to the regression analysis of competing-risks data. Attention is focused on inference concerning the effects of factors on both the probability of occurrence and the hazard rate conditional on each of the failure types. These two quantities are specified in the mixture model using the logistic model and the proportional hazards model, respectively. We propose a semi-parametric mixture method to estimate the logistic and regression coefficients jointly, whereby the component-baseline hazard functions are completely unspecified. Estimation is based on maximum likelihood on the basis of the full likelihood, implemented via an expectation-conditional maximization (ECM) algorithm. Simulation studies are performed to compare the performance of the proposed semi-parametric method with a fully parametric mixture approach. The results show that when the component-baseline hazard is monotonic increasing, the semi-parametric and fully parametric mixture approaches are comparable for mildly and moderately censored samples. When the component-baseline hazard is not monotonic increasing, the semi-parametric method consistently provides less biased estimates than a fully parametric approach and is comparable in efficiency in the estimation of the parameters for all levels of censoring. The methods are illustrated using a real data set of prostate cancer patients treated with different dosages of the drug diethylstilbestrol. Copyright (C) 2003 John Wiley Sons, Ltd.