MOTIVATION: The object of this study is to propose a new method to identify small compact units that compose protein three-dimensional structures. These fragments, called 'protein units (PU)', are a new level of description to well understand and analyze the organization of protein structures. The method only works from the contact probability matrix, i.e. the inter Calpha-distances translated into probabilities. It uses the principle of conventional hierarchical clustering, leading to a series of nested partitions of the 3D structure. Every step aims at dividing optimally a unit into 2 or 3 subunits according to a criterion called 'partition index' assessing the structural independence of the subunits newly defined. Moreover, an entropy-derived squared correlation R is used for assessing globally the protein structure dissection. The method is compared to other splitting algorithms and shows relevant performance. AVAILABILITY: An Internet server with dedicated tools is available at http://www.ebgm.jussieu.fr/~gelly/

MOTIVATION: Molecular evolution, which is classically assessed by comparison of individual proteins or genes between species, can now be studied by comparing co-expressed functional groups of genes. This approach, which better reflects the functional constraints on the evolution of organisms, can exploit the large amount of data generated by genome-wide expression analyses. However, it requires new methodologies to represent the data in a more accessible way for cross-species comparisons. RESULTS: In this work, we present an approach based on Multi-dimensional Scaling techniques, to compare the conformation of two gene expression networks, represented in a multi-dimensional space. The expression networks are optimally superimposed, taking into account two criteria: (1) inter-organism orthologous gene pairs have to be nearby points in the final multi-dimensional space and (2) the distortion of the gene expression networks, the organization of which reflects the similarities between the gene expression measurements, has to be circumscribed. Using this approach, we compared the transcriptional programs that drive sporulation in budding and fission yeasts, extracting some common properties and differences between the two species.

BACKGROUND: Microarray technologies produced large amount of data. The hierarchical clustering is commonly used to identify clusters of co-expressed genes. However, microarray datasets often contain missing values (MVs) representing a major drawback for the use of the clustering methods. Usually the MVs are not treated, or replaced by zero or estimated by the k-Nearest Neighbor (kNN) approach. The topic of the paper is to study the stability of gene clusters, defined by various hierarchical clustering algorithms, of microarrays experiments including or not MVs. RESULTS: In this study, we show that the MVs have important effects on the stability of the gene clusters. Moreover, the magnitude of the gene misallocations is depending on the aggregation algorithm. The most appropriate aggregation methods (e.g. complete-linkage and Ward) are highly sensitive to MVs, and surprisingly, for a very tiny proportion of MVs (e.g. 1%). In most of the case, the MVs must be replaced by expected values. The MVs replacement by the kNN approach clearly improves the identification of co-expressed gene clusters. Nevertheless, we observe that kNN approach is less suitable for the extreme values of gene expression. CONCLUSION: The presence of MVs (even at a low rate) is a major factor of gene cluster instability. In addition, the impact depends on the hierarchical clustering algorithm used. Some methods should be used carefully. Nevertheless, the kNN approach constitutes one efficient method for restoring the missing expression gene values, with a low error level. Our study highlights the need of statistical treatments in microarray data to avoid misinterpretation.

MOTIVATION: Our aim is to develop a process that automatically defines a repertory of contiguous 3D protein structure fragments and can be used in homology modeling. We present here improvements to the method we introduced previously: the 'hybrid protein model' (de Brevern and Hazout, THEOR: Chem. Acc., 106, 36-47, (2001)) The hybrid protein learns a non-redundant databank encoded in a structural alphabet composed of 16 Protein Blocks (PBs; de Brevern et al., Proteins, 41, 271-287, (2000)). Every local fold is learned by looking for the most similar pattern present in the hybrid protein and modifying it slightly. Finally each position corresponds to a cluster of similar 3D local folds. RESULTS: In this paper, we describe improvements to our method for building an optimal hybrid protein: (i) 'baby training,' which is defined as the introduction of large structure fragments and the progressive reduction in the size of training fragments; and (ii) the deletion of the redundant parts of the hybrid protein. This repertory of contiguous 3D protein structure fragments should be a useful tool for molecular modeling.

MOTIVATION: Locating the regions of similarity in a genome requires the availability of appropriate tools such as 'Accelerated Search for SImilar Regions in Chromosomes' (ASSIRC; Vincens et al., Bioinformatics, 14, 715-725, 1998). The aim of this paper is to present different strategies for improving this program by distributing the operations and data to multiple processing units and to assess the efficiency of the different implementations in terms of running time as a function of the number of processing units. RESULTS: The new version D-ASSIRCis based on three alternative strategies of task sharing: (1) a distributed search using the splitting of studied sequences into large overlapping subsequences (strategy ASS); (2) two distributed searches for repeated exact motifs of fixed size either managed by a central processor (strategy AGD) or locally managed by numerous processors (strategy ALD). The result is that the strategy ASSis suitable for a large number of processing units (the time was divided by a factor of 12 when the number of processing units was increased from 1 to 16) wheras the strategy ALDis better for a small set of processors (typically for four or six). The different proposed strategies are efficient for various applications in genomic research, particularly for locating similarities of nucleic sequences in large genomes. AVAILABILITY: D-ASSIRCis freely available by anonymous FTP at ftp://ftp.ens.fr/pub/molbio/dassirc.tar.gz. Sources and binaries for Solaris and Linux are included in the distribution.

Abstract Summary: MOSAIC is a set of tools for the segmentation of multiple aligned DNA sequences into homogeneous zones. The segmentation is based on the distribution of mutational events along the alignment. As an example, the analysis of one repeated sequence belonging to the subtelomeric regions of the yeast genome is presented. Availability: Free access from ftp://ftp.biomath.jussieu.fr/pub/papers/MOSAIC Contact: [email protected] * To whom correspondence should be addressed.

The transformation of protein 1D-sequence to protein 3D-structure is one of the main difficulties of structural biology. A structural alphabet has been previously defined from dihedral angles describing the protein backbone as structural information by using an unsupervised classifier. The 16 protein blocks (PBs), basis element of the structural alphabet, allows a correct 3D structure approximation. Local prediction had been estimated by a Bayesian approach and shown that sequence information induces strongly the local fold, but stays coarse (prediction rate of 40.7% with one PB, 75,8% with the four most probable PBs). The Hybrid Protein Model presented in this study learns both the sequence and structure of the proteins. The analysis made along the hybrid protein has permitted to appreciate more precisely the spatial location of some types of amino acid residues in the secondary structures and their flanking regions. This study leads to a fuzzy model of dependence between sequence and structure.

UNLABELLED: PredAcc is a tool for predicting the solvent accessibility of protein residues from the sequence at different relative accessibility levels (0-55%). The prediction rate varies between 70. 7% (for 25% relative accessibility) and 85.7% (for 0% relative accessibility). Amino acids are predicted in four categories: almost certainly hidden and almost certainly exposed with a given a posteriori prediction error, probably hidden and probably exposed otherwise. AVAILABILITY: http://condor.urbb.jussieu.fr/PredAccCfg.html CONTACT: [email protected]

Motivation: The approaches usually used for building large genetic maps consist of dividing the marker set into linkage groups and provide local orders that can be tested by multi-point linkage analysis. To deal with the limitations of these approaches, a strategy taking the marker set into account globally is defined. Results: The paper presents a new approach called 'Bi-Dimensional Scaling Map (BDS-Map) for inferring marker orders and distances in genetic maps based on the use of an additional dimension orthogonal to the map into which markers are projected. Dynamical forces based on a two-point analysis are applied to tend to optimize the marker locations in space. The efficiency of the approach is exemplified on real data (16 and 70 markers on chromosomes 6 and 2, respectively) and simulated data (50 maps of 70 markers). Availability: The package called ANGE (ANalyse du GE-nome), including both the program BDS-Map and the system allowing the database management, is available on request from the authors. Contact: E-mail:[email protected]

A homogeneous region in a protein sequence is a set of contiguous residues that share common features, concerning physico-chemical, structural and mutational information. This paper presents a method for identifying such homogeneous regions. From a profile describing a given type of biological information along the sequence, the algorithm allows the segmentation of the sequence by optimizing a criterion characterized by two user-defined control parameters: the 'homogenizing degree' of the regions and the 'site neighbourhood' size. We apply the method to the envelope proteins of the human immunodeficiency virus HIV-1, for the identification of homogeneous regions in a hydrophobicity profile and the delineation of variable and conserved regions in a variability profile.

This paper presents a method for the multiple alignment of a sequence set. The MASH algorithm uses a non-redundant database of common motifs and an 'alignment priority' criterion that depends on the length and the occurrence frequency of the patterns in the set of sequences. This user-defined criterion allows the determination of the series of the patterns to be aligned. This program is applied to a fragment of envelope gene env gp120 for 20 isolates of the immunodeficiency virus. The multiplicity of alignments obtained by modifying the criterion parameters reveals different aspects of similarity between the sequences.

We propose a new method, called 'size leap' algorithm, of search for motifs of maximum size and common to two fragments at least. It allows the creation of a reduced database of motifs from a set of sequences whose size obeys the series of Fibonacci numbers. The convenience lies in the efficiency of the motif extraction. It can be applied in the establishment of overlap regions for DNA sequence reconstruction and multiple alignment of biological sequences. The method of complete DNA sequence reconstruction by extraction of the longest motifs ('anchor motifs') is presented as an application of the size leap algorithm. The details of a reconstruction from three sequenced fragments are given as an example.

We have developed a new algorithm 'Complete sentences compatibility' (CSC) which uses single and double digestion fragments to rapidly determine restriction maps of circular DNA. From possible combinations of fragments of each simple digestion, which we call 'sentences of decomposition', we construct a restriction map which combines the sentences while taking into account compatibility rules. The algorithm can also deal with experimental errors of fragment weight and can suggest solutions that account for non-readable bands (fragments of zero length or multiple bands) on the gel. Because experiments using pairs of restrictive enzymes often result in multiple solutions, a complementary algorithm tries to reduce the number of proposed solutions by establishing consensus maps. The restriction map construction algorithm was tested on real cases, some containing more than fifteen fragments. Execution times range from 1-10 s on an IBM PC compatible microcomputer.