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 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.

Use of the EM algorithm to detect QTL affecting multiple-traits in an across half-sib family analysis

QTL detection experiments in livestock species commonly use the half-sib design. Each male is mated to a number of females, each female producing a limited number of progeny. Analysis consists of attempting to detect associations between phenotype and genotype measured on the progeny. When family sizes are limiting experimenters may wish to incorporate as much information as possible into a single analysis. However, combining information across sires is problematic because of incomplete linkage disequilibrium between the markers and the QTL in the population. This study describes formulae for obtaining MLEs via the expectation maximization (EM) algorithm for use in a multiple-trait, multiple-family analysis. A model specifying a QTL with only two alleles, and a common within sire error variance is assumed. Compared to single-family analyses, power can be improved up to fourfold with multi-family analyses. The accuracy and precision of QTL location estimates are also substantially improved. With small family sizes, the multi-family, multi-trait analyses reduce substantially, but not totally remove, biases in QTL effect estimates. In situations where multiple QTL alleles are segregating the multi-family analysis will average out the effects of the different QTL alleles.

A gradient descent algorithm for minimizing amino acid coupling reactions when synthesizing cyclic-peptide libraries

Combinatorial chemistry has become an invaluable tool in medicinal chemistry for the identification of new drug leads. For example, libraries of predetermined sequences and head-to-tail cyclized peptides are routinely synthesized in our laboratory using the IRORI approach. Such libraries are used as molecular toolkits that enable the development of pharmacophores that define activity and specificity at receptor targets. These libraries can be quite large and difficult to handle, due to physical and chemical constraints imposed by their size. Therefore, smaller sub-libraries are often targeted for synthesis. The number of coupling reactions required can be greatly reduced if the peptides having common amino acids are grouped into the same sub-library (batching). This paper describes a schedule optimizer to minimize the number of coupling reactions by rotating and aligning sequences while simultaneously batching. The gradient descent method thereby reduces the number of coupling reactions required for synthesizing cyclic peptide libraries. We show that the algorithm results in a 75% reduction in the number of coupling reactions for a typical cyclic peptide library.

Common multiples of complete graphs

A graph H is said to divide a graph G if there exists a set S of subgraphs of G, all isomorphic to H, such that the edge set of G is partitioned by the edge sets of the subgraphs in S. Thus, a graph G is a common multiple of two graphs if each of the two graphs divides G.

XSophe-Sophe-XeprView (R). A computer simulation software suite (v. 1.1.3) for the analysis of continuous wave EPR spectra

The XSophe-Sophe-XeprView((R)) computer simulation software suite enables scientists to easily determine spin Hamiltonian parameters from isotropic, randomly oriented and single crystal continuous wave electron paramagnetic resonance (CW EPR) spectra from radicals and isolated paramagnetic metal ion centers or clusters found in metalloproteins, chemical systems and materials science. XSophe provides an X-windows graphical user interface to the Sophe programme and allows: creation of multiple input files, local and remote execution of Sophe, the display of sophelog (output from Sophe) and input parameters/files. Sophe is a sophisticated computer simulation software programme employing a number of innovative technologies including; the Sydney OPera HousE (SOPHE) partition and interpolation schemes, a field segmentation algorithm, the mosaic misorientation linewidth model, parallelization and spectral optimisation. In conjunction with the SOPHE partition scheme and the field segmentation algorithm, the SOPHE interpolation scheme and the mosaic misorientation linewidth model greatly increase the speed of simulations for most spin systems. Employing brute force matrix diagonalization in the simulation of an EPR spectrum from a high spin Cr(III) complex with the spin Hamiltonian parameters g(e) = 2.00, D = 0.10 cm(-1), E/D = 0.25, A(x) = 120.0, A(y) = 120.0, A(z) = 240.0 x 10(-4) cm(-1) requires a SOPHE grid size of N = 400 (to produce a good signal to noise ratio) and takes 229.47 s. In contrast the use of either the SOPHE interpolation scheme or the mosaic misorientation linewidth model requires a SOPHE grid size of only N = 18 and takes 44.08 and 0.79 s, respectively. Results from Sophe are transferred via the Common Object Request Broker Architecture (CORBA) to XSophe and subsequently to XeprView((R)) where the simulated CW EPR spectra (1D and 2D) can be compared to the experimental spectra. Energy level diagrams, transition roadmaps and transition surfaces aid the interpretation of complicated randomly oriented CW EPR spectra and can be viewed with a web browser and an OpenInventor scene graph viewer.

An improved seeded region growing algorithm

Recently Adams and Bischof (1994) proposed a novel region growing algorithm for segmenting intensity images. The inputs to the algorithm are the intensity image and a set of seeds - individual points or connected components - that identify the individual regions to be segmented. The algorithm grows these seed regions until all of the image pixels have been assimilated. Unfortunately the algorithm is inherently dependent on the order of pixel processing. This means, for example, that raster order processing and anti-raster order processing do not, in general, lead to the same tessellation. In this paper we propose an improved seeded region growing algorithm that retains the advantages of the Adams and Bischof algorithm fast execution, robust segmentation, and no tuning parameters - but is pixel order independent. (C) 1997 Elsevier Science B.V.

FRA10B structure reveals common elements in repeat expansion and chromosomal fragile site genesis

A common mechanism for chromosomal fragile site genesis is not yet apparent. Folate-sensitive fragile sites are expanded p(CCG)n repeats that arise from longer normal alleles. Distamycin A or bromodeoxyuridine-inducible fragile site FRA16B is an expanded AT-rich similar to 33 bp repeat; however, the relationship between normal and fragile site alleles is not known. Here, we report that bromodeoxyuridine-inducible, distamycin A-insensitive fragile site FRA10B is composed of expanded similar to 42 bp repeats. Differences in repeat motif length or composition between different FRA10B families indicate multiple independent expansion events. Some FRA10B alleles comprise a mixture of different expanded repeat motifs. FRA10B fragile site and long normal alleles share flanking polymorphisms. Somatic and intergenerational FRA10B repeat instability analogous to that found in expanded trinucleotide repeats supports dynamic mutation as a common mechanism for repeat expansion.

Prediction of MHC class II-binding peptides using an evolutionary algorithm and artificial neural network

Motivation: Prediction methods for identifying binding peptides could minimize the number of peptides required to be synthesized and assayed, and thereby facilitate the identification of potential T-cell epitopes. We developed a bioinformatic method for the prediction of peptide binding to MHC class II molecules. Results: Experimental binding data and expert knowledge of anchor positions and binding motifs were combined with an evolutionary algorithm (EA) and an artificial neural network (ANN): binding data extraction --> peptide alignment --> ANN training and classification. This method, termed PERUN, was implemented for the prediction of peptides that bind to HLA-DR4(B1*0401). The respective positive predictive values of PERUN predictions of high-, moderate-, low- and zero-affinity binder-a were assessed as 0.8, 0.7, 0.5 and 0.8 by cross-validation, and 1.0, 0.8, 0.3 and 0.7 by experimental binding. This illustrates the synergy between experimentation and computer modeling, and its application to the identification of potential immunotheraaeutic peptides.

Dysregulated hematopoiesis and a progressive neurological disorder induced by expression of an activated form of the human common beta chain in transgenic mice

Previously we described activating mutations of h beta(c), the common signaling subunit of the receptors for the hematopoietic and inflammatory cytokines, GM-CSF, IL-3, and IL-5. The activated mutant, h beta(c)FI Delta, is able to confer growth factor-independent proliferation on the murine myeloid cell line FDC-P1, and on primary committed myeloid progenitors. We have used this activating mutation to study the effects of chronic cytokine receptor stimulation. Transgenic mice were produced carrying the h beta(c)FI Delta cDNA linked to the constitutive promoter derived from the phosphoglycerate kinase gene, PGK-1. Transgene expression was demonstrated in several tissues and functional activity of the mutant receptor was confirmed in hematopoietic tissues by the presence of granulocyte macrophage and macrophage colony-forming cells (CFU-GM and CFU-M) in the absence of added cytokines. All transgenic mice display a myeloproliferative disorder characterized by splenomegaly, erythrocytosis, and granulocytic and megakaryocytic hyperplasia. This disorder resembles the human disease polycythemia vera, suggesting that activating mutations in h beta(c) may play a role in the pathogenesis of this myeloproliferative disorder. In addition, these transgenic mice develop a sporadic, progressive neurological disease and display bilateral, symmetrical foci of necrosis in the white matter of brain stem associated with an accumulation of macrophages. Thus, chronic h beta(c) activation has the potential to contribute to pathological events in the central nervous system.

The common tetratricopeptide repeat acceptor site for steroid receptor-associated immunophilins and Hop is located in the dimerization domain of hsp90

Structurally related tetratricopeptide repeat motifs in steroid receptor-associated immunophilins and the STI1 homolog, Hop, mediate the interaction with a common cellular target, hsp90, We have identified the binding domain in hsp90 for cyclophilin 40 (CyP40) using a two-hybrid system screen of a mouse cDNA library. All isolated clones encoded the intact carboxyl terminus of hsp90 and overlapped with a common region corresponding to amino acids 558-724 of murine hsp84, The interaction was confirmed in vitro with bacterially expressed CyP40 and deletion mutants of hsp90 beta and was delineated further to a 124-residue COOH-terminal segment of hsp90, Deletion of the conserved MEEVD sequence at the extreme carboxyl terminus of hsp90 precludes interaction with CyP40, signifying an important role for this motif in hsp90 function. We show that CyP40 and Hop display similar interaction profiles with hsp90 truncation mutants and present evidence for the direct competition of Hop and FK506-binding protein 52 with CyP40 for binding to the hsp90 COOH-terminal region. Our results are consistent with a common tetratricopeptide repeat interaction site for Hop and steroid receptor associated immunophilins within a discrete COOH-terminal domain of hsp90. This region of hsp90 mediates ATP-independent chaperone activity, overlaps the hsp90 dimerization domain, and includes structural elements important for steroid receptor interaction.

A cell type-specific constitutive point mutant of the common beta-subunit of the human granulocyte-macrophage colony-stimulating factor (GM-CSF), interleukin (IL)-3, and IL-5 receptors requires the GM-CSF receptor alpha-subunit for activation

The high affinity receptor for human granulocyte-macrophage colony-stimulating factor (GM-CSF) consists of a cytokine-specific alpha-subunit (hGMR alpha) and a common signal-transducing beta-subunit (hpc) that is shared with the interleukin-3 and -5 receptors, We have previously identified a constitutively active extracellular point mutant of hpc, I374N, that can confer factor independence on murine FDC-P1 cells but not BAF-B03 or CTLL-2 cells (Jenkins, B. J., D'Andrea, R. J., and Gonda, T. J. (1995) EMBO J. 14, 4276-4287), This restricted activity suggested the involvement of cell type-specific signaling molecules in the activation of this mutant. We report here that one such molecule is the mouse GMR alpha (mGMR alpha) subunit, since introduction of mGMR alpha, but not hGMR alpha, into BAF-B03 or CTLL-2 cells expressing the I374N mutant conferred factor independence, Experiments utilizing mouse/human chimeric GMR alpha subunits indicated that the species specificity lies in the extracellular domain of GMRa. Importantly, the requirement for mGMR alpha correlated with the ability of I374N (but not wild-type hpc) to constitutively associate with mGMRa. Expression of I374N in human factor-dependent UT7 cells also led to factor-independent proliferation, with concomitant up-regulation of hGMR alpha surface expression. Taken together, these findings suggest a critical role for association with GMR alpha in the constitutive activity of I374N.