2009-11-21T06:28:43Zhttp://open-archive.highwire.org/handler

oai:open-archive.highwire.org:bioinfo:23/18/23612007-09-17HighWireOUPbioinfo:23:18

The global trace graph, a novel paradigm for searching protein sequence databases Heger, Andreas Mallick, Swapan Wilton, Christopher Holm, Liisa SEQUENCE ANALYSIS Motivation: Propagating functional annotations to sequence-similar, presumably homologous proteins lies at <cross-ref type="fn" refid="FN1"></cross-ref>the <cross-ref type="fn" refid="FN2"></cross-ref>heart <cross-ref type="fn" refid="FN3"></cross-ref>of the bioinformatics industry. Correct propagation is crucially dependent on the accurate identification of subtle sequence motifs that are conserved in evolution. The evolutionary signal can be difficult to detect because functional sites may consist of non-contiguous residues while segments in-between may be mutated without affecting fold or function. Results: Here, we report a novel graph clustering algorithm in which all known protein sequences simultaneously self-organize into hypothetical multiple sequence alignments. This eliminates noise so that non-contiguous sequence motifs can be tracked down between extremely distant homologues. The novel data structure enables fast sequence database searching methods which are superior to profile-profile comparison at recognizing distant homologues. This study will boost the leverage of structural and functional genomics and opens up new avenues for data mining a complete set of functional signature motifs. Availability: <inter-ref locator="http://www.bioinfo.biocenter.helsinki.fi/gtg" locator-type="url">http://www.bioinfo.biocenter.helsinki.fi/gtg</inter-ref> Contact: <inter-ref locator="liisa.holm@helsinki.fi" locator-type="email">liisa.holm@helsinki.fi</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2361 http://dx.doi.org/10.1093/bioinformatics/btm358 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/23682007-09-17HighWireOUPbioinfo:23:18

A quantitative genotype algorithm reflecting H5N1 Avian influenza niches Wan, Xiu-Feng Chen, Guorong Luo, Feng Emch, Michael Donis, Ruben PHYLOGENETICS Motivation: Computational genotyping analyses are critical for characterizing molecular evolutionary footprints, thus providing important information for designing the strategies of influenza prevention and control. Most of the current methods that are available are based on multiple sequence alignment and phylogenetic tree construction, which are time consuming and limited by the number of taxa. Arbitrarily defining genotypes further complicates the interpretation of genotyping results. Methods: In this study, we describe a quantitative influenza genotyping algorithm based on the theory of quasispecies. First, the complete composition vector (CCV) was utilized to calculate the pairwise evolutionary distance between genotypes. Next, Hierarchical Bayesian Modeling using the Gibbs Sampling algorithm was applied to identify the segment genotype threshold, which is used to identify influenza segment genotype through a modularity calculation. The viral genotype was defined by combining eight segment genotypes based on the genetic reassortment feature of influenza A viruses. Results: We applied this method for H5N1 avian influenza viruses and identified 107 niches among 283 viruses with a complete genome set. The diversity of viral genotypes, and their correlation with geographic locations suggests that these viruses form local niches after being introduced to a new ecological environment through poultry trade or bird migration. This novel method allows us to define genotypes in a robust, quantitative as well as hierarchical manner. Contact: <inter-ref locator="wanhenry@yahoo.com" locator-type="email">wanhenry@yahoo.com</inter-ref> or <inter-ref locator="fvq7@cdc.gov" locator-type="email">fvq7@cdc.gov</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2368 http://dx.doi.org/10.1093/bioinformatics/btm354 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/23532007-09-17HighWireOUPbioinfo:23:18

Methods of remote homology detection can be combined to increase coverage by 10% in the midnight zone Reid, Adam James Yeats, Corin Orengo, Christine Anne SEQUENCE ANALYSIS Motivation: A recent development in sequence-based remote homologue detection is the introduction of profile–profile comparison methods. These are more powerful than previous technologies and can detect potentially homologous relationships missed by structural classifications such as CATH and SCOP. As structural classifications traditionally act as the gold standard of homology this poses a challenge in benchmarking them. Results: We present a novel approach which allows an accurate benchmark of these methods against the CATH structural classification. We then apply this approach to assess the accuracy of a range of publicly available methods for remote homology detection including several profile–profile methods (COMPASS, HHSearch, PRC) from two perspectives. First, in distinguishing homologous domains from non-homologues and second, in annotating proteomes with structural domain families. PRC is shown to be the best method for distinguishing homologues. We show that SAM is the best practical method for annotating genomes, whilst using COMPASS for the most remote homologues would increase coverage. Finally, we introduce a simple approach to increase the sensitivity of remote homologue detection by up to 10 %. This is achieved by combining multiple methods with a jury vote. Contact: <inter-ref locator="reid@bioichem.ucl.ac.uk" locator-type="email">reid@bioichem.ucl.ac.uk</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2353 http://dx.doi.org/10.1093/bioinformatics/btm355 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24332007-09-17HighWireOUPbioinfo:23:18

Modular decomposition of metabolic reaction networks based on flux analysis and pathway projection Yoon, Jeongah Si, Yaguang Nolan, Ryan Lee, Kyongbum SYSTEMS BIOLOGY Motivation: The rational decomposition of biochemical networks into sub-structures has emerged as a useful approach to study the design of these complex systems. A biochemical network is characterized by an inhomogeneous connectivity distribution, which gives rise to several organizational features, including modularity. To what extent the connectivity-based modules reflect the functional organization of the network remains to be further explored. In this work, we examine the influence of physiological perturbations on the modular organization of cellular metabolism. Results: Modules were characterized for two model systems, liver and adipocyte primary metabolism, by applying an algorithm for top–down partition of directed graphs with non-uniform edge weights. The weights were set by the engagement of the corresponding reactions as expressed by the flux distribution. For the base case of the fasted rat liver, three modules were found, carrying out the following biochemical transformations: ketone body production, glucose synthesis and transamination. This basic organization was further modified when different flux distributions were applied that describe the liver's metabolic response to whole body inflammation. For the fully mature adipocyte, only a single module was observed, integrating all of the major pathways needed for lipid storage. Weaker levels of integration between the pathways were found for the early stages of adipocyte differentiation. Our results underscore the inhomogeneous distribution of both connectivity and connection strengths, and suggest that global activity data such as the flux distribution can be used to study the organizational flexibility of cellular metabolism. Contact: <inter-ref locator="kyongbum.lee@tufts.edu" locator-type="email">kyongbum.lee@tufts.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2433 http://dx.doi.org/10.1093/bioinformatics/btm374 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24412007-09-17HighWireOUPbioinfo:23:18

Quantitative quality-assessment techniques to compare fractionation and depletion methods in SELDI-TOF mass spectrometry experiments Harezlak, Jaroslaw Wang, Mike Christiani, David Lin, Xihong DATA AND TEXT MINING Motivation: Mass spectrometry (MS), such as the surface-enhanced laser desorption and ionization time-of-flight (SELDI-TOF) MS, provides a potentially promising proteomic technology for biomarker discovery. An important matter for such a technology to be used routinely is its reproducibility. It is of significant interest to develop quantitative measures to evaluate the quality and reliability of different experimental methods. Results: We compare the quality of SELDI-TOF MS data using unfractionated, fractionated plasma samples and abundant protein depletion methods in terms of the numbers of detected peaks and reliability. Several statistical quality-control and quality-assessment techniques are proposed, including the Graeco–Latin square design for the sample allocation on a Protein chip, the use of the pairwise Pearson correlation coefficient as the similarity measure between the spectra in conjunction with multi-dimensional scaling (MDS) for graphically evaluating similarity of replicates and assessing outlier samples; and the use of the reliability ratio for evaluating reproducibility. Our results show that the number of peaks detected is similar among the three sample preparation technologies, and the use of the Sigma multi-removal kit does not improve peak detection. Fractionation of plasma samples introduces more experimental variability. The peaks detected using the unfractionated plasma samples have the highest reproducibility as determined by the reliability ratio. Availability: Our algorithm for assessment of SELDI-TOF experiment quality is available at <inter-ref locator="http://www.biostat.harvard.edu/~xlin" locator-type="url">http://www.biostat.harvard.edu/~xlin</inter-ref> Contact: <inter-ref locator="harezlak@post.harvard.edu" locator-type="email">harezlak@post.harvard.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2441 http://dx.doi.org/10.1093/bioinformatics/btm346 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/23762007-09-17HighWireOUPbioinfo:23:18

Natively unstructured regions in proteins identified from contact predictions Schlessinger, Avner Punta, Marco Rost, Burkhard STRUCTURAL BIOINFORMATICS Motivation: Natively unstructured (also dubbed <it>intrinsically disordered</it>) regions in proteins lack a defined 3D structure under physiological conditions and often adopt regular structures under particular conditions. Proteins with such regions are overly abundant in eukaryotes, they may increase functional complexity of organisms and they usually evade structure determination in the unbound form. Low propensity for the formation of internal residue contacts has been previously used to predict natively unstructured regions. Results: We combined PROFcon predictions for protein-specific contacts with a generic pairwise potential to predict unstructured regions. This novel method, <it>Ucon</it>, outperformed the best available methods in predicting proteins with long unstructured regions. Furthermore, <it>Ucon</it> correctly identified cases missed by other methods. By computing the difference between predictions based on specific contacts (approach introduced here) and those based on generic potentials (realized in other methods), we might identify unstructured regions that are involved in protein–protein binding. We discussed one example to illustrate this ambitious aim. Overall, Ucon added quality and an orthogonal aspect that may help in the experimental study of unstructured regions in network hubs. Availability: <inter-ref locator="http://www.predictprotein.org/submit_ucon.html" locator-type="url">http://www.predictprotein.org/submit_ucon.html</inter-ref> Contact: <inter-ref locator="as2067@columbia.edu" locator-type="email">as2067@columbia.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2376 http://dx.doi.org/10.1093/bioinformatics/btm349 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/23852007-09-17HighWireOUPbioinfo:23:18

AffyProbeMiner: a web resource for computing or retrieving accurately redefined Affymetrix probe sets Liu, Hongfang Zeeberg, Barry R. Qu, Gang Koru, A. Gunes Ferrucci, Alessandro Kahn, Ari Ryan, Michael C. Nuhanovic, Antej Munson, Peter J. Reinhold, William C. Kane, David W. Weinstein, John N. GENE EXPRESSION Motivation: Affymetrix microarrays are widely used to measure global expression of mRNA transcripts. That technology is based on the concept of a probe set. Individual probes within a probe set were originally designated by Affymetrix to hybridize with the same unique mRNA transcript. Because of increasing accuracy in knowledge of genomic sequences, however, a substantial number of the manufacturer's original probe groupings and mappings are now known to be inaccurate and must be corrected. Otherwise, analysis and interpretation of an Affymetrix microarray experiment will be in error. Results: AffyProbeMiner is a computationally efficient platform-independent tool that uses all RefSeq mature RNA protein coding transcripts and validated complete coding sequences in GenBank to (1) regroup the individual probes into consistent probe sets and (2) remap the probe sets to the correct sets of mRNA transcripts. The individual probes are grouped into probe sets that are ‘transcript-consistent’ in that they hybridize to the same mRNA transcript (or transcripts) and, therefore, measure the same entity (or entities). About 65.6 % of the probe sets on the HG-U133A chip were affected by the remapping. Pre-computed regrouped and remapped probe sets for many Affymetrix microarrays are made freely available at the AffyProbeMiner web site. Alternatively, we provide a web service that enables the user to perform the remapping for any type of short-oligo commercial or custom array that has an Affymetrix-format Chip Definition File (CDF). Important features that differentiate AffyProbeMiner from other approaches are flexibility in the handling of splice variants, computational efficiency, extensibility, customizability and user-friendliness of the interface. Availability: The web interface and software (GPL open source license), are publicly-accessible at <inter-ref locator="http://discover.nci.nih.gov/affyprobeminer" locator-type="url">http://discover.nci.nih.gov/affyprobeminer</inter-ref>. Contact: <inter-ref locator="hl224@georgetown.edu" locator-type="email">hl224@georgetown.edu</inter-ref> or <inter-ref locator="barry@discover.nci.nih.gov" locator-type="email">barry@discover.nci.nih.gov</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2385 http://dx.doi.org/10.1093/bioinformatics/btm360 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/23912007-09-17HighWireOUPbioinfo:23:18

Selection and validation of normalization methods for c-DNA microarrays using within-array replications Fan, Jianqing Niu, Yue GENE EXPRESSION Motivation: Normalization of microarray data is essential for multiple-array analyses. Several normalization protocols have been proposed based on different biological or statistical assumptions. A fundamental problem arises whether they have effectively normalized arrays. In addition, for a given array, the question arises how to choose a method to most effectively normalize the microarray data. Results: We propose several techniques to compare the effectiveness of different normalization methods. We approach the problem by constructing statistics to test whether there are any systematic biases in the expression profiles among duplicated spots within an array. The test statistics involve estimating the genewise variances. This is accomplished by using several novel methods, including empirical Bayes methods for moderating the genewise variances and the smoothing methods for aggregating variance information. <it>P</it>-values are estimated based on a normal or χ approximation. With estimated <it>P</it>-values, we can choose a most appropriate method to normalize a specific array and assess the extent to which the systematic biases due to the variations of experimental conditions have been removed. The effectiveness and validity of the proposed methods are convincingly illustrated by a carefully designed simulation study. The method is further illustrated by an application to human placenta cDNAs comprising a large number of clones with replications, a customized microarray experiment carrying just a few hundred genes on the study of the molecular roles of Interferons on tumor, and the Agilent microarrays carrying tens of thousands of total RNA samples in the MAQC project on the study of reproducibility, sensitivity and specificity of the data. Availability: Code to implement the method in the statistical package R is available from the authors. Contact: <inter-ref locator="jqfan@princeton.edu" locator-type="email">jqfan@princeton.edu</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2391 http://dx.doi.org/10.1093/bioinformatics/btm361 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24152007-09-17HighWireOUPbioinfo:23:18

Robustness analysis and tuning of synthetic gene networks Batt, Grégory Yordanov, Boyan Weiss, Ron Belta, Calin SYSTEMS BIOLOGY Motivation: The goal of synthetic biology is to design and construct biological systems that present a desired behavior. The construction of synthetic gene networks implementing simple functions has demonstrated the feasibility of this approach. However, the design of these networks is difficult, notably because existing techniques and tools are not adapted to deal with uncertainties on molecular concentrations and parameter values. Results: We propose an approach for the analysis of a class of uncertain piecewise-multiaffine differential equation models. This modeling framework is well adapted to the experimental data currently available. Moreover, these models present interesting mathematical properties that allow the development of efficient algorithms for solving robustness analyses and tuning problems. These algorithms are implemented in the tool RoVerGeNe, and their practical applicability and biological relevance are demonstrated on the analysis of the tuning of a synthetic transcriptional cascade built in <it>Escherichia coli</it>. Availability: RoVerGeNe and the transcriptional cascade model are available at <inter-ref locator="http://iasi.bu.edu/%7Ebatt/rovergene/rovergene.htm" locator-type="url">http://iasi.bu.edu/%7Ebatt/rovergene/rovergene.htm</inter-ref> Contact: <inter-ref locator="gregory.batt@imag.fr" locator-type="email">gregory.batt@imag.fr</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2415 http://dx.doi.org/10.1093/bioinformatics/btm362 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24072007-09-17HighWireOUPbioinfo:23:18

LICORN: learning cooperative regulation networks from gene expression data Elati, Mohamed Neuvial, Pierre Bolotin-Fukuhara, Monique Barillot, Emmanuel Radvanyi, François Rouveirol, Céline SYSTEMS BIOLOGY Motivation: One of the most challenging tasks in the post-genomic era is the reconstruction of transcriptional regulation networks. The goal is to identify, for each gene expressed in a particular cellular context, the regulators affecting its transcription, and the co-ordination of several regulators in specific types of regulation. DNA microarrays can be used to investigate relationships between regulators and their target genes, through simultaneous observations of their RNA levels. Results: We propose a <it>data mining</it> system for inferring transcriptional regulation relationships from RNA expression values. This system is particularly suitable for the detection of cooperative transcriptional regulation. We model regulatory relationships as labelled two-layer gene regulatory networks, and describe a method for the efficient learning of these bipartite networks from discretized expression data sets. We also evaluate the statistical significance of such inferred networks and validate our methods on two public yeast expression data sets. Availability: <inter-ref locator="http://www.lri.fr/~elati/licorn.html" locator-type="url">http://www.lri.fr/~elati/licorn.html</inter-ref> Contact: <inter-ref locator="mohamed.elati@curie.fr" locator-type="email">mohamed.elati@curie.fr</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2407 http://dx.doi.org/10.1093/bioinformatics/btm352 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/23992007-09-17HighWireOUPbioinfo:23:18

Haplotype inference for present absent genotype data using previously identified haplotypes and haplotype patterns Yoo, Yun Joo Tang, Jianming Kaslow, Richard A. Zhang, Kui GENETICS AND POPULATION ANALYSIS Motivation: Killer immunoglobulin-like receptor (KIR) genes vary considerably in their presence or absence on a specific regional haplotype. Because presence or absence of these genes is largely detected using locus-specific genotyping technology, the distinction between homozygosity and hemizygosity is often ambiguous. The performance of methods for haplotype inference (e.g. PL-EM, PHASE) for KIR genes may be compromised due to the large portion of ambiguous data. At the same time, many haplotypes or partial haplotype patterns have been previously identified and can be incorporated to facilitate haplotype inference for unphased genotype data. To accommodate the increased ambiguity of present–absent genotyping of KIR genes, we developed a hybrid approach combining a greedy algorithm with the Expectation-Maximization (EM) method for haplotype inference based on previously identified haplotypes and haplotype patterns. Results: We implemented this algorithm in a software package named HAPLO-IHP (Haplotype inference using identified haplotype patterns) and compared its performance with that of HAPLORE and PHASE on simulated KIR genotypes. We compared five measures in order to evaluate the reliability of haplotype assignments and the accuracy in estimating haplotype frequency. Our method outperformed the two existing techniques by all five measures when either 60 % or 25 % of previously identified haplotypes were incorporated into the analyses. Availability: The HAPLO-IHP is available at <inter-ref locator="http://www.soph.uab.edu/Statgenetics/People/KZhang/HAPLO-IHP/index.html" locator-type="url">http://www.soph.uab.edu/Statgenetics/People/KZhang/HAPLO-IHP/index.html</inter-ref> Contact: <inter-ref locator="KZhang@ms.soph.uab.edu" locator-type="email">KZhang@ms.soph.uab.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2399 http://dx.doi.org/10.1093/bioinformatics/btm371 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24232007-09-17HighWireOUPbioinfo:23:18

miniTUBA: medical inference by network integration of temporal data using Bayesian analysis Xiang, Zuoshuang Minter, Rebecca M. Bi, Xiaoming Woolf, Peter J. He, Yongqun SYSTEMS BIOLOGY Motivation: Many biomedical and clinical research problems involve discovering causal relationships between observations gathered from temporal events. Dynamic Bayesian networks are a powerful modeling approach to describe causal or apparently causal relationships, and support complex medical inference, such as future response prediction, automated learning, and rational decision making. Although many engines exist for creating Bayesian networks, most require a local installation and significant data manipulation to be practical for a general biologist or clinician. No software pipeline currently exists for interpretation and inference of dynamic Bayesian networks learned from biomedical and clinical data. Results: miniTUBA is a web-based modeling system that allows clinical and biomedical researchers to perform complex medical/clinical inference and prediction using dynamic Bayesian network analysis with temporal datasets. The software allows users to choose different analysis parameters (e.g. Markov lags and prior topology), and continuously update their data and refine their results. miniTUBA can make temporal predictions to suggest interventions based on an automated learning process pipeline using all data provided. Preliminary tests using synthetic data and laboratory research data indicate that miniTUBA accurately identifies regulatory network structures from temporal data. Availability: miniTUBA is available at <inter-ref locator="http://www.minituba.org" locator-type="url">http://www.minituba.org</inter-ref> Contact: <inter-ref locator="yongqunh@med.umich.edu" locator-type="email">yongqunh@med.umich.edu</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2423 http://dx.doi.org/10.1093/bioinformatics/btm372 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24632007-09-17HighWireOUPbioinfo:23:18

Robust smooth segmentation approach for array CGH data analysis Huang, Jian Gusnanto, Arief O'Sullivan, Kathleen Staaf, Johan Borg, Åke Pawitan, Yudi DATA AND TEXT MINING Motivation: Array comparative genomic hybridization (aCGH) provides a genome-wide technique to screen for copy number alteration. The existing segmentation approaches for analyzing aCGH data are based on modeling data as a series of discrete segments with unknown boundaries and unknown heights. Although the biological process of copy number alteration is discrete, in reality a variety of biological and experimental factors can cause the signal to deviate from a stepwise function. To take this into account, we propose a smooth segmentation (smoothseg) approach. Methods: To achieve a robust segmentation, we use a doubly heavy-tailed random-effect model. The first heavy-tailed structure on the errors deals with outliers in the observations, and the second deals with possible jumps in the underlying pattern associated with different segments. We develop a fast and reliable computational procedure based on the iterative weighted least-squares algorithm with band-limited matrix inversion. Results: Using simulated and real data sets, we demonstrate how smoothseg can aid in identification of regions with genomic alteration and in classification of samples. For the real data sets, smoothseg leads to smaller false discovery rate and classification error rate than the circular binary segmentation (CBS) algorithm. In a realistic simulation setting, smoothseg is better than wavelet smoothing and CBS in identification of regions with genomic alterations and better than CBS in classification of samples. For comparative analyses, we demonstrate that segmenting the <it>t</it>-statistics performs better than segmenting the data. Availability: The R package <ty>smoothseg</ty> to perform smooth segmentation is available from <inter-ref locator="http://www.meb.ki.se/~yudpaw" locator-type="url">http://www.meb.ki.se/~yudpaw</inter-ref> Contact: <inter-ref locator="yudi.pawitan@ki.se" locator-type="email">yudi.pawitan@ki.se</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2463 http://dx.doi.org/10.1093/bioinformatics/btm359 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24772007-09-17HighWireOUPbioinfo:23:18

Medline search engine for finding genetic markers with biological significance Xuan, Weijian Wang, Pinglang Watson, Stanley J. Meng, Fan DATA AND TEXT MINING Motivation: Genome-wide high density SNP association studies are expected to identify various SNP alleles associated with different complex disorders. Understanding the biological significance of these SNP alleles in the context of existing literature is a major challenge since existing search engines are not designed to search literature for SNPs or other genetic markers. The literature mining of gene and protein functions has received significant attention and effort while similar work on genetic markers and their related diseases is still in its infancy. Our goal is to develop a web-based tool that facilitates the mining of Medline literature related to genetic studies and gene/protein function studies. Our solution consists of four main function modules for (1) identification of different types of genetic markers or genetic variations in Medline records (2) distinguishing positive versus negative linkage or association between genetic markers and diseases (3) integrating marker genomic location data from different databases to enable the retrieval of Medline records related to markers in the same linkage disequilibrium region (4) and a web interface called MarkerInfoFinder to search, display, sort and download Medline citation results. Tests using published data suggest MarkerInfoFinder can significantly increase the efficiency of finding genetic disorders and their underlying molecular mechanisms. The functions we developed will also be used to build a knowledge base for genetic markers and diseases. Availability: The MarkerInfoFinder is publicly available at: <inter-ref locator="http://brainarray.mbni.med.umich.edu/brainarray/datamining/MarkerInfoFinder" locator-type="url">http://brainarray.mbni.med.umich.edu/brainarray/datamining/MarkerInfoFinder</inter-ref> Contact: <inter-ref locator="mengf@umich.edu" locator-type="email">mengf@umich.edu</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2477 http://dx.doi.org/10.1093/bioinformatics/btm375 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24492007-09-17HighWireOUPbioinfo:23:18

An approach to predict transcription factor DNA binding site specificity based upon gene and transcription factor functional categorization Qian, Ziliang Lu, Lingyi Liu, XiaoJun Cai, Yu-Dong Li, Yixue DATA AND TEXT MINING Motivation: To understand transcription regulatory mechanisms, it is indispensable to investigate transcription factor (TF) DNA binding preferences. We noted that the generally acknowledged information of functional annotations of TFs as well as that of their target genes should provide useful hints in determining TF DNA binding preferences. Results: In this contribution, we developed an integrative method based on the Nearest Neighbor Algorithm, to predict DNA binding preferences through integrating both the functional/structural information of TFs and the interaction between TFs and their targets. The accuracy of cross-validation tests on the dataset consisting of 3430 positive samples and 7000 negative samples reaches 87.0 % for 10-fold cross-validation and 87.9 % for jackknife cross-validation test, which is a much better result than that in our previous work. The prediction result indicates that the improved method we developed could be a powerful approach to infer the TF DNA preference <it>in silico</it>. Contact: <inter-ref locator="cyd@picb.ac.cn" locator-type="email">cyd@picb.ac.cn</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2449 http://dx.doi.org/10.1093/bioinformatics/btm348 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24702007-09-17HighWireOUPbioinfo:23:18

Analysis of array CGH data for cancer studies using fused quantile regression Li, Youjuan Zhu, Ji DATA AND TEXT MINING Motivation: The identification of DNA copy number changes provides insights that may advance our understanding of initiation and progression of cancer. Array-based comparative genomic hybridization (array-CGH) has emerged as a technique allowing high-throughput genome-wide scanning for chromosomal aberrations. A number of statistical methods have been proposed for the analysis of array-CGH data. In this article, we consider a fused quantile regression model based on three motivations: (1) quantile regression may provide a more comprehensive picture for the ratio profile of copy numbers than the standard mean regression approach; (2) for simplicity, most available methods assume uniform spacing between neighboring clones, while incorporating the information of physical locations of clones may be helpful and (3) most current methods have a set of tuning parameters that must be carefully tuned, which introduces complexity to the implementation. Results: We formulate the detection of regions of gains and losses in a fused regularized quantile regression framework, incorporating physical locations of clones. We derive an efficient algorithm that computes the entire solution path for the resulting optimization problem, and we propose a simple estimate for the complexity of the fitted model, which leads to convenient selection of the tuning parameter. Three published array-CGH datasets are used to demonstrate our approach. Availability: R code are available at <inter-ref locator="http://www.stat.lsa.umich.edu/~jizhu/code/cgh/" locator-type="url">http://www.stat.lsa.umich.edu/~jizhu/code/cgh/</inter-ref> Contact: <inter-ref locator="jizhu@umich.edu" locator-type="email">jizhu@umich.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2470 http://dx.doi.org/10.1093/bioinformatics/btm364 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24882007-09-17HighWireOUPbioinfo:23:18

Quality estimation of multiple sequence alignments by Bayesian hypothesis testing Tomovic, Andrija Oakeley, Edward J. SEQUENCE ANALYSIS Summary: In this work we present a web-based tool for estimating multiple alignment quality using Bayesian hypothesis testing. The proposed method is very simple, easily implemented and not time consuming with a linear complexity. We evaluated method against a series of different alignments (a set of random and biologically derived alignments) and compared the results with tools based on classical statistical methods (such as sFFT and csFFT). Taking correlation coefficient as an objective criterion of the true quality, we found that Bayesian hypothesis testing performed better on average than the classical methods we tested. This approach may be used independently or as a component of any tool in computational biology which is based on the statistical estimation of alignment quality. Availability: <inter-ref locator="http://www.fmi.ch/groups/functional.genomics/tool.htm" locator-type="url">http://www.fmi.ch/groups/functional.genomics/tool.htm</inter-ref> Contact: <inter-ref locator="edward.oakeley@fmi.ch" locator-type="email">edward.oakeley@fmi.ch</inter-ref> Supplementary information: Supplementary data are available from <inter-ref locator="http://www.fmi.ch/groups/functional.genomics/tool-Supp.htm" locator-type="url">http://www.fmi.ch/groups/functional.genomics/tool-Supp.htm</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2488 http://dx.doi.org/10.1093/bioinformatics/btm366 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24852007-09-17HighWireOUPbioinfo:23:18

HMMoC a compiler for hidden Markov models Lunter, Gerton SEQUENCE ANALYSIS Summary: Hidden Markov models are widely applied within computational biology. The large data sets and complex models involved demand optimized implementations, while efficient exploration of model space requires rapid prototyping. These requirements are not met by existing solutions, and hand-coding is time-consuming and error-prone. Here, I present a compiler that takes over the mechanical process of implementing HMM algorithms, by translating high-level XML descriptions into efficient C++ implementations. The compiler is highly customizable, produces efficient and bug-free code, and includes several optimizations. Availability: <inter-ref locator="http://genserv.anat.ox.ac.uk/software" locator-type="url">http://genserv.anat.ox.ac.uk/software</inter-ref> Contact: <inter-ref locator="gerton.lunter@dpag.ox.ac.uk" locator-type="email">gerton.lunter@dpag.ox.ac.uk</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2485 http://dx.doi.org/10.1093/bioinformatics/btm350 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24552007-09-17HighWireOUPbioinfo:23:18

Mining complex genotypic features for predicting HIV-1 drug resistance Saigo, Hiroto Uno, Takeaki Tsuda, Koji DATA AND TEXT MINING Motivation: Human immunodeficiency virus type 1 (HIV-1) evolves in human body, and its exposure to a drug often causes mutations that enhance the resistance against the drug. To design an effective pharmacotherapy for an individual patient, it is important to accurately predict the drug resistance based on genotype data. Notably, the resistance is not just the simple sum of the effects of all mutations. Structural biological studies suggest that the association of mutations is crucial: even if mutations A or B alone do not affect the resistance, a significant change might happen when the two mutations occur together. Linear regression methods cannot take the associations into account, while decision tree methods can reveal only limited associations. Kernel methods and neural networks implicitly use all possible associations for prediction, but cannot select salient associations explicitly. Results: Our method, <it>itemset boosting</it>, performs linear regression in the complete space of power sets of mutations. It implements a forward feature selection procedure where, in each iteration, one mutation combination is found by an efficient branch-and-bound search. This method uses all possible combinations, and salient associations are explicitly shown. In experiments, our method worked particularly well for predicting the resistance of nucleotide reverse transcriptase inhibitors (NRTIs). Furthermore, it successfully recovered many mutation associations known in biological literature. Availability: <inter-ref locator="http://www.kyb.mpg.de/bs/people/hiroto/iboost/" locator-type="url">http://www.kyb.mpg.de/bs/people/hiroto/iboost/</inter-ref> Contact: <inter-ref locator="koji.tsuda@tuebingen.mpg.de" locator-type="email">koji.tsuda@tuebingen.mpg.de</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2455 http://dx.doi.org/10.1093/bioinformatics/btm353 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24912007-09-17HighWireOUPbioinfo:23:18

Con-Struct Map: a comparative contact map analysis tool Chung, Jo-Lan Beaver, John E. Scheeff, Eric D. Bourne, Philip E. STRUCTURAL BIOINFORMATICS Summary: Con-Struct Map is a graphical tool for the comparative study of protein structures. The tool detects potential conserved residue contacts shared by multiple protein structures by superimposing their contact maps according to a multiple structure alignment. In general, Con-Struct Map allows the study of structural changes resulting from, e.g. sequence substitutions, or alternatively, the study of conserved components of a structure framework across structurally aligned proteins. Specific applications include the study of sequence-structure relationship in distantly related proteins and the comparisons of wild type and mutant proteins. Availability: <inter-ref locator="http://pdbrs3.sdsc.edu/ConStructMap/viewer_argument_generator/singleArguments" locator-type="url">http://pdbrs3.sdsc.edu/ConStructMap/viewer_argument_generator/singleArguments</inter-ref> Contact: <inter-ref locator="bourne@sdsc.edu" locator-type="email">bourne@sdsc.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2491 http://dx.doi.org/10.1093/bioinformatics/btm356 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/25012007-09-17HighWireOUPbioinfo:23:18

EcoProDB: the Escherichia coli protein database Yun, Hongseok Lee, Jeong Wook Jeong, Joonwoo Chung, Jaesung Park, Jong Myoung Myoung, Han Na Lee, Sang Yup DATABASES AND ONTOLOGIES Summary: EcoProDB is a web-based database for comparative proteomics of <it>Escherichia coli</it>. The database contains information on <it>E. coli</it> proteins identified on 2D gels along with other resources collected from various databases and published literature, with a special feature of showing the expression levels of <it>E. coli</it> proteins under different genetic and environmental conditions. It also provides comparative information of subcellular localization, theoretical 2D map, experimental 2D map and integrated protein information via an interactive web interface and application such as the Map Browser. Users can also upload their own 2D gels, extract core information associated with the proteins and 2D gel results from different experiments and consequently generate new knowledge and hypotheses for further studies. Availability: EcoProDB database system is accessible at <inter-ref locator="http://eecoli.kaist.ac.kr" locator-type="url">http://eecoli.kaist.ac.kr</inter-ref> Contact: <inter-ref locator="leesy@kaist.ac.kr" locator-type="email">leesy@kaist.ac.kr</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2501 http://dx.doi.org/10.1093/bioinformatics/btm351 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24932007-09-17HighWireOUPbioinfo:23:18

RefPlus: an R package extending the RMA Algorithm Harbron, Chris Chang, Kai-Ming South, Marie C. GENE EXPRESSION Summary: RMA has become a widely used methodology to pre-process Affymetrix gene expression microarrays. A limitation of RMA is that the calculated probeset intensities change when a set of microarrays is re-pre-processed after the inclusion of additional microarrays into the analysis set. Here we report the availability of the RefPlus package containing functions to perform the Extrapolation Strategy and Extrapolation Averaging algorithms which address these issues. Availability: The software is implemented in the R language and can be downloaded from the Bioconductor project website (<inter-ref locator="http://www.bioconductor.org" locator-type="url">http://www.bioconductor.org</inter-ref>). Contact: <inter-ref locator="Chris.Harbron@AstraZeneca.Com" locator-type="email">Chris.Harbron@AstraZeneca.Com</inter-ref> Supplementary information: Further details of the workings and evaluation of these functions are given in the documentation available on the Bioconductor website. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2493 http://dx.doi.org/10.1093/bioinformatics/btm357 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24982007-09-17HighWireOUPbioinfo:23:18

sMOL Explorer: an open source, web-enabled database and exploration tool for Small MOLecules datasets Ingsriswang, Supawadee Pacharawongsakda, Eakasit DATA AND TEXT MINING Summary: sMOL Explorer is a 2D ligand-based computational tool that provides three major functionalities: data management, information retrieval and extraction and statistical analysis and data mining through Web interface. With sMOL Explorer, users can create personal databases by adding each small molecule via a drawing interface or uploading the data files from internal and external projects into the sMOL database. Then, the database can be browsed and queried with textual and structural similarity search. The molecule can also be submitted to search against external public databases including PubChem, KEGG, DrugBank and eMolecules. Moreover, users can easily access a variety of data mining tools from Weka and R packages to perform analysis including (1) finding the frequent substructure, (2) clustering the molecular fingerprints, (3) identifying and removing irrelevant attributes from the data and (4) building the classification model of biological activity. Availability: sMOL Explorer is an Open Source project and is freely available to all interested users at <inter-ref locator="http://www.biotec.or.th/ISL/SMOL/" locator-type="url">http://www.biotec.or.th/ISL/SMOL/</inter-ref> Contact: <inter-ref locator="supawadee@biotec.or.th" locator-type="email">supawadee@biotec.or.th</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2498 http://dx.doi.org/10.1093/bioinformatics/btm363 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/25042007-09-17HighWireOUPbioinfo:23:18

A Laboratory Information Management System (LIMS) for a high throughput genetic platform aimed at candidate gene mutation screening Voegele, C. Tavtigian, S.V. de Silva, D. Cuber, S. Thomas, A. Le Calvez-Kelm, F. DATABASES AND ONTOLOGIES Summary: High throughput mutation screening in an automated environment generates large data sets that have to be organized and stored reliably. Complex multistep workflows require strict process management and careful data tracking. We have developed a Laboratory Information Management Systems (LIMS) tailored to high throughput candidate gene mutation scanning and resequencing that respects these requirements. Designed with a client/server architecture, our system is platform independent and based on open-source tools from the database to the web application development strategy. Flexible, expandable and secure, the LIMS, by communicating with most of the laboratory instruments and robots, tracks samples and laboratory information, capturing data at every step of our automated mutation screening workflow. An important feature of our LIMS is that it enables tracking of information through a laboratory workflow where the process at one step is contingent on results from a previous step. Availability: Script for MySQL database table creation and source code of the whole JSP application are freely available on our website: <inter-ref locator="http://www-gcs.iarc.fr/lims/" locator-type="url">http://www-gcs.iarc.fr/lims/</inter-ref>. Contact: <inter-ref locator="voegele@iarc.fr" locator-type="email">voegele@iarc.fr</inter-ref> Supplementary information: System server configuration, database structure and additional details on the LIMS and the mutation screening workflow are available on our website: <inter-ref locator="http://www-gcs.iarc.fr/lims/" locator-type="url">http://www-gcs.iarc.fr/lims/</inter-ref> Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2504 http://dx.doi.org/10.1093/bioinformatics/btm365 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/18/24952007-09-17HighWireOUPbioinfo:23:18

APID2NET: unified interactome graphic analyzer Hernandez-Toro, Juan Prieto, Carlos De Las Rivas, Javier SYSTEMS BIOLOGY Motivation: Exploration and analysis of interactome networks at systems level requires unification of the biomolecular elements and annotations that come from many different high-throughput or small-scale proteomic experiments. Only such integration can provide a non-redundant and consistent identification of proteins and interactions. APID2NET is a new tool that works with Cytoscape to allow surfing unified interactome data by querying APID server (<inter-ref locator="http://bioinfow.dep.usal.es/apid/" locator-type="url">http://bioinfow.dep.usal.es/apid/</inter-ref>) to provide interactive analysis of protein–protein interaction (PPI) networks. The program is designed to visualize, explore and analyze the proteins and interactions retrieved, including the annotations and attributes associated to them, such as: GO terms, InterPro domains, experimental methods that validate each interaction, PubMed IDs, UniProt IDs, etc. The tool provides interactive graphical representation of the networks with all Cytoscape capabilities, plus new automatic tools to find concurrent functional and structural attributes along all protein pairs in a network. Availability: <inter-ref locator="http://bioinfow.dep.usal.es/apid/apid2net.html" locator-type="url">http://bioinfow.dep.usal.es/apid/apid2net.html</inter-ref> Contact: <inter-ref locator="jrivas@usal.es" locator-type="email">jrivas@usal.es</inter-ref> Supplementary information: Installation Guide and User's Guide are supplied at the Web site indicated above. Oxford University Press 2007-09-17 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/18/2495 http://dx.doi.org/10.1093/bioinformatics/btm373 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5382007-03-21HighWireOUPbioinfo:23:5

Improving the accuracy of transmembrane protein topology prediction using evolutionary information Jones, David T. SEQUENCE ANALYSIS Motivation: Many important biological processes such as cell signaling, transport of membrane-impermeable molecules, cell–cell communication, cell recognition and cell adhesion are mediated by membrane proteins. Unfortunately, as these proteins are not water soluble, it is extremely hard to experimentally determine their structure. Therefore, improved methods for predicting the structure of these proteins are vital in biological research. In order to improve transmembrane topology prediction, we evaluate the combined use of both integrated signal peptide prediction and evolutionary information in a single algorithm. Results: A new method (MEMSAT3) for predicting transmembrane protein topology from sequence profiles is described and benchmarked with full cross-validation on a standard data set of 184 transmembrane proteins. The method is found to predict both the correct topology and the locations of transmembrane segments for 80% of the test set. This compares with accuracies of 62–72% for other popular methods on the same benchmark. By using a second neural network specifically to discriminate transmembrane from globular proteins, a very low overall false positive rate (0.5%) can also be achieved in detecting transmembrane proteins. Availability: An implementation of the described method is available both as a web server (<inter-ref locator="http://www.psipred.net" locator-type="url">http://www.psipred.net</inter-ref>) and as downloadable source code from <inter-ref locator="http://bioinf.cs.ucl.ac.uk/memsat" locator-type="url">http://bioinf.cs.ucl.ac.uk/memsat</inter-ref>. Both the server and source code files are free to non-commercial users. Benchmark and training data are also available from <inter-ref locator="http://bioinf.cs.ucl.ac.uk/memsat" locator-type="url">http://bioinf.cs.ucl.ac.uk/memsat</inter-ref>. Contact: <inter-ref locator="dtj@cs.ucl.ac.uk" locator-type="email">dtj@cs.ucl.ac.uk</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/538 http://dx.doi.org/10.1093/bioinformatics/btl677 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5272007-03-21HighWireOUPbioinfo:23:5

I-Ssp6803I: the first homing endonuclease from the PD-(D/E)XK superfamily exhibits an unusual mode of DNA recognition Orlowski, Jerzy Boniecki, Michal Bujnicki, Janusz M. STRUCTURAL BIOINFORMATICS Motivation: Restriction endonucleases (REases) and homing endonucleases (HEases) are biotechnologically important enzymes. Nearly all structurally characterized REases belong to the PD-(D/E)XK superfamily of nucleases, while most HEases belong to an unrelated LAGLIDADG superfamily. These two protein folds are typically associated with very different modes of protein-DNA recognition, consistent with the different mechanisms of action required to achieve high specificity. REases recognize short DNA sequences using multiple contacts per base pair, while HEases recognize very long sites using a few contacts per base pair, thereby allowing for partial degeneracy of the target sequence. Thus far, neither REases with the LAGLIDADG fold, nor HEases with the PD-(D/E)XK fold, have been found. Results: Using protein fold recognition, we have identified the first member of the PD-(D/E)XK superfamily among homing endonucleases, a cyanobacterial enzyme I-Ssp6803I. We present a model of the I-Ssp6803I-DNA complex based on the structure of Type II restriction endonuclease R.BglI and predict the active site and residues involved in specific DNA sequence recognition by I-Ssp6803I. Our finding reveals a new unexpected evolutionary link between HEases and REases and suggests how PD-(D/E)XK nucleases may develop a ‘HEase-like’ way of interacting with the extended DNA sequence. This in turn may be exploited to study the evolution of DNA sequence specificity and to engineer nucleases with new substrate specificities. Contact: <inter-ref locator="iamb@genesilico.pl" locator-type="email">iamb@genesilico.pl</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/527 http://dx.doi.org/10.1093/bioinformatics/btm007 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5552007-03-21HighWireOUPbioinfo:23:5

A new protein-protein docking scoring function based on interface residue properties Bernauer, J. Azé, J. Janin, J. Poupon, A. STRUCTURAL BIOINFORMATICS Motivation: Protein–protein complexes are known to play key roles in many cellular processes. However, they are often not accessible to experimental study because of their low stability and difficulty to produce the proteins and assemble them in native conformation. Thus, docking algorithms have been developed to provide an <it>in silico</it> approach of the problem. A protein–protein docking procedure traditionally consists of two successive tasks: a search algorithm generates a large number of candidate solutions, and then a scoring function is used to rank them. Results: To address the second step, we developed a scoring function based on a Voronoï tessellation of the protein three-dimensional structure. We showed that the Voronoï representation may be used to describe in a simplified but useful manner, the geometric and physico-chemical complementarities of two molecular surfaces. We measured a set of parameters on native protein–protein complexes and on decoys, and used them as attributes in several statistical learning procedures: a logistic function, Support Vector Machines (SVM), and a genetic algorithm. For the later, we used ROGER, a genetic algorithm designed to optimize the area under the receiver operating characteristics curve. To further test the scores derived with ROGER, we ranked models generated by two different docking algorithms on targets of a blind prediction experiment, improving in almost all cases the rank of native-like solutions. Availability: <inter-ref locator="http://genomics.eu.org/spip/-Bioinformatics-tools-" locator-type="url">http://genomics.eu.org/spip/-Bioinformatics-tools-</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/555 http://dx.doi.org/10.1093/bioinformatics/btl654 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5452007-03-21HighWireOUPbioinfo:23:5

The Treeterbi and Parallel Treeterbi algorithms: efficient, optimal decoding for ordinary, generalized and pair HMMs Keibler, Evan Arumugam, Manimozhiyan Brent, Michael R. SEQUENCE ANALYSIS Motivation: Hidden Markov models (HMMs) and generalized HMMs been successfully applied to many problems, but the standard Viterbi algorithm for computing the most probable interpretation of an input sequence (known as decoding) requires memory proportional to the length of the sequence, which can be prohibitive. Existing approaches to reducing memory usage either sacrifice optimality or trade increased running time for reduced memory. Results: We developed two novel decoding algorithms, Treeterbi and Parallel Treeterbi, and implemented them in the TWINSCAN/N-SCAN gene-prediction system. The worst case asymptotic space and time are the same as for standard Viterbi, but in practice, Treeterbi optimally decodes arbitrarily long sequences with generalized HMMs in bounded memory without increasing running time. Parallel Treeterbi uses the same ideas to split optimal decoding across processors, dividing latency to completion by approximately the number of available processors with constant average overhead per processor. Using these algorithms, we were able to optimally decode all human chromosomes with N-SCAN, which increased its accuracy relative to heuristic solutions. We also implemented Treeterbi for Pairagon, our pair HMM based cDNA-to-genome aligner. Availability: The TWINSCAN/N-SCAN/PAIRAGON open source software package is available from <inter-ref locator="http://genes.cse.wustl.edu" locator-type="url">http://genes.cse.wustl.edu</inter-ref>. Contact: <inter-ref locator="brent@cse.wustl.edu" locator-type="email">brent@cse.wustl.edu</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/545 http://dx.doi.org/10.1093/bioinformatics/btl659 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5312007-03-21HighWireOUPbioinfo:23:5

Computing exact P-values for DNA motifs Zhang, Jing Jiang, Bo Li, Ming Tromp, John Zhang, Xuegong Zhang, Michael Q. SEQUENCE ANALYSIS Motivation: Many heuristic algorithms have been designed to approximate <it>P</it>-values of DNA motifs described by position weight matrices, for evaluating their statistical significance. They often significantly deviate from the true <it>P</it>-value by orders of magnitude. Exact <it>P</it>-value computation is needed for ranking the motifs. Furthermore, surprisingly, the complexity of the problem is unknown. Results: We show the problem to be NP-hard, and present MotifRank, software based on dynamic programming, to calculate exact <it>P</it>-values of motifs. We define the exact <it>P</it>-value on a general and more precise model. Asymptotically, MotifRank is faster than the best exact <it>P</it>-value computing algorithm, and is in fact practical. Our experiments clearly demonstrate that MotifRank significantly improves the accuracy of existing approximation algorithms. Availability: MotifRank is available from <inter-ref locator="http://bio.dlg.cn" locator-type="url">http://bio.dlg.cn</inter-ref> Contact: <inter-ref locator="mzhang@cshl.edu" locator-type="email">mzhang@cshl.edu</inter-ref> <inter-ref locator="mli@uwaterloo.ca" locator-type="email">mli@uwaterloo.ca</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/531 http://dx.doi.org/10.1093/bioinformatics/btl662 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6272007-03-21HighWireOUPbioinfo:23:5

SNPchip: R classes and methods for SNP array data Scharpf, Robert B. Ting, Jason C. Pevsner, Jonathan Ruczinski, Ingo GENOME ANALYSIS Summary: High-density single nucleotide polymorphism microarrays (SNP chips) provide information on a subject's genome, such as copy number and genotype (heterozygosity/homozygosity) at a SNP. While fluorescence <it>in situ</it> hybridization and karyotyping reveal many abnormalities, SNP chips provide a higher resolution map of the human genome that can be used to detect, e.g., aneuploidies, microdeletions, microduplications and loss of heterozygosity (LOH). As a variety of diseases are linked to such chromosomal abnormalities, SNP chips promise new insights for these diseases by aiding in the discovery of such regions, and may suggest targets for intervention. The R package <it>SNPchip</it> contains classes and methods useful for storing, visualizing and analyzing high density SNP data. Originally developed from the SNPscan web-tool, <it>SNPchip</it> utilizes S4 classes and extends other open source R tools available at Bioconductor. This has numerous advantages, including the ability to build statistical models for SNP-level data that operate on instances of the class, and to communicate with other R packages that add additional functionality. Availability: The package is available from the Bioconductor web page at <inter-ref locator="www.bioconductor.org" locator-type="url">www.bioconductor.org</inter-ref> Contact: <inter-ref locator="ingo@jhu.edu" locator-type="email">ingo@jhu.edu</inter-ref> Supplementary information: The supplementary material as described in this article (case studies, installation guidelines and R code) is available from <inter-ref locator="http://biostat.jhsph.edu/~iruczins/publications/sm/" locator-type="url">http://biostat.jhsph.edu/~iruczins/publications/sm/</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/627 http://dx.doi.org/10.1093/bioinformatics/btl638 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5822007-03-21HighWireOUPbioinfo:23:5

Analysis of E.coli promoter recognition problem in dinucleotide feature space Rani, T. Sobha Bhavani, S. Durga Bapi, Raju S. STRUCTURAL BIOINFORMATICS Motivation: Patterns in the promoter sequences within a species are known to be conserved but there exist many exceptions to this rule which makes the promoter recognition a complex problem. Although many complex feature extraction schemes coupled with several classifiers have been proposed for promoter recognition in the current literature, the problem is still open. Results: A dinucleotide global feature extraction method is proposed for the recognition of sigma-70 promoters in <it>Escherichia coli</it> in this article. The positive data set consists of sigma-70 promoters with known transcription starting points which are part of regulonDB and promec databases. Four different kinds of negative data sets are considered, two of them biological sets (Gordon <it>et al</it>., <cross-ref type="bib" refid="B5">2003</cross-ref>) and the other two synthetic data sets. Our results reveal that a single-layer perceptron using dinucleotide features is able to achieve an accuracy of 80% against a background of biological non-promoters and 96% for random data sets. A scheme for locating the promoter regions in a given genome sequence is proposed. A deeper analysis of the data set shows that there is a bifurcation of the data set into two distinct classes, a majority class and a minority class. Our results point out that majority class constituting the majority promoter and the majority non-promoter signal is linearly separable. Also the minority class is linearly separable. We further show that the feature extraction and classification methods proposed in the paper are generic enough to be applied to the more complex problem of eucaryotic promoter recognition. We present Drosophila promoter recognition as a case study. Availability: <inter-ref locator="http://202.41.85.117/htmfiles/faculty/tsr/tsr.html" locator-type="url">http://202.41.85.117/htmfiles/faculty/tsr/tsr.html</inter-ref> Contact: <inter-ref locator="tsrcs@uohyd.ernet.in" locator-type="email">tsrcs@uohyd.ernet.in</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/582 http://dx.doi.org/10.1093/bioinformatics/btl670 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6052007-03-21HighWireOUPbioinfo:23:5

Comparison of human protein-protein interaction maps Futschik, Matthias E. Chaurasia, Gautam Herzel, Hanspeter SYSTEMS BIOLOGY Motivation: Large-scale mappings of protein–protein interactions have started to give us new views of the complex molecular mechanisms inside a cell. After initial projects to systematically map protein interactions in model organisms such as yeast, worm and fly, researchers have begun to focus on the mapping of the human interactome. To tackle this enormous challenge, different approaches have been proposed and pursued. While several large-scale human protein interaction maps have recently been published, their quality remains to be critically assessed. Results: We present here a first comparative analysis of eight currently available large-scale maps with a total of over 10 000 unique proteins and 57 000 interactions included. They are based either on literature search, orthology or by yeast-two-hybrid assays. Comparison reveals only a small, but statistically significant overlap. More importantly, our analysis gives clear indications that all interaction maps imply considerable selection and detection biases. These results have to be taken into account for future assembly of the human interactome. Availability: An integrated human interaction network called Unified Human Interactome (<it>UniHI</it>) is made publicly accessible at <inter-ref locator="http://www.mdc-berlin.de/unihi" locator-type="url">http://www.mdc-berlin.de/unihi</inter-ref>. Contact: <inter-ref locator="m.futschik@biologie.hu-berlin.de" locator-type="email">m.futschik@biologie.hu-berlin.de</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/605 http://dx.doi.org/10.1093/bioinformatics/btl683 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6122007-03-21HighWireOUPbioinfo:23:5

Speeding up tandem mass spectrometry database search: metric embeddings and fast near neighbor search Dutta, Debojyoti Chen, Ting DATA AND TEXT MINING Motivation: Due to the recent advances in technology of mass spectrometry, there has been an exponential increase in the amount of data being generated in the past few years. Database searches have not been able to keep with this data explosion. Thus, speeding up the data searches becomes increasingly important in mass-spectrometry-based applications. Traditional database search methods use one-against-all comparisons of a query spectrum against a very large number of peptides generated from <it>in silico</it> digestion of protein sequences in a database, to filter potential candidates from this database followed by a detailed scoring and ranking of those filtered candidates. Results: In this article, we show that we can avoid the one-against-all comparisons. The basic idea is to design a set of hash functions to pre-process peptides in the database such that for each query spectrum we can use the hash functions to find only a small subset of peptide sequences that are most likely to match the spectrum. The construction of each hash function is based on a random spectrum and the hash value of a peptide is the normalized shared peak counts score (cosine) between the random spectrum and the hypothetical spectrum of the peptide. To implement this idea, we first embed each peptide into a unit vector in a high-dimensional metric space. The random spectrum is represented by a random vector, and we use random vectors to construct a set of hash functions called locality sensitive hashing (LSH) for preprocessing. We demonstrate that our mapping is accurate. We show that our method can filter out >95.65% of the spectra without missing any correct sequences, or gain 111 times speedup by filtering out 99.64% of spectra while missing at most 0.19% (2 out of 1014) of the correct sequences. In addition, we show that our method can be effectively used for other mass spectra mining applications such as finding clusters of spectra efficiently and accurately. Contact: <inter-ref locator="tingchen@usc.edu" locator-type="email">tingchen@usc.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/612 http://dx.doi.org/10.1093/bioinformatics/btl645 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6192007-03-21HighWireOUPbioinfo:23:5

Peak selection from MALDI-TOF mass spectra using ant colony optimization Ressom, H. W. Varghese, R. S. Drake, S. K. Hortin, G. L. Abdel-Hamid, M. Loffredo, C. A. Goldman, R. DATA AND TEXT MINING Motivation: Due to the large number of peaks in mass spectra of low-molecular-weight (LMW) enriched sera, a systematic method is needed to select a parsimonious set of peaks to facilitate biomarker identification. We present computational methods for matrix-assisted laser desorption/ionization time-of-flight (MALDI-TOF) spectral data preprocessing and peak selection. In particular, we propose a novel method that combines ant colony optimization (ACO) with support vector machines (SVM) to select a small set of useful peaks. Results: The proposed hybrid ACO-SVM algorithm selected a panel of eight peaks out of 228 candidate peaks from MALDI-TOF spectra of LMW enriched sera. An SVM classifier built with these peaks achieved 94% sensitivity and 100% specificity in distinguishing hepatocellular carcinoma from cirrhosis in a blind validation set of 69 samples. Area under the receiver operating characteristic (ROC) curve was 0.996. The classification capability of these peaks is compared with those selected by the SVM-recursive feature elimination method. Availability: Supplementary material and MATLAB scripts to implement the methods described in this article are available at <inter-ref locator="http://microarray.georgetown.edu/web/files/bioinf.htm" locator-type="url">http://microarray.georgetown.edu/web/files/bioinf.htm</inter-ref> Contact: <inter-ref locator="hwr@georgetown.edu" locator-type="email">hwr@georgetown.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/619 http://dx.doi.org/10.1093/bioinformatics/btl678 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5972007-03-21HighWireOUPbioinfo:23:5

Protein-protein interaction site prediction based on conditional random fields Li, Ming-Hui Lin, Lei Wang, Xiao-Long Liu, Tao SYSTEMS BIOLOGY Motivation: We are motivated by the fast-growing number of protein structures in the Protein Data Bank with necessary information for prediction of protein–protein interaction sites to develop methods for identification of residues participating in protein–protein interactions. We would like to compare conditional random fields (CRFs)-based method with conventional classification-based methods that omit the relation between two labels of neighboring residues to show the advantages of CRFs-based method in predicting protein–protein interaction sites. Results: The prediction of protein–protein interaction sites is solved as a sequential labeling problem by applying CRFs with features including protein sequence profile and residue accessible surface area. The CRFs-based method can achieve a comparable performance with state-of-the-art methods, when 1276 nonredundant hetero-complex protein chains are used as training and test set. Experimental result shows that CRFs-based method is a powerful and robust protein–protein interaction site prediction method and can be used to guide biologists to make specific experiments on proteins. Availability: <inter-ref locator="http://www.insun.hit.edu.cn/~mhli/site_CRFs/index.html" locator-type="url">http://www.insun.hit.edu.cn/~mhli/site_CRFs/index.html</inter-ref> Contact: <inter-ref locator="mhli@insun.hit.edu.cn" locator-type="email">mhli@insun.hit.edu.cn</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/597 http://dx.doi.org/10.1093/bioinformatics/btl660 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5732007-03-21HighWireOUPbioinfo:23:5

Structure-based evaluation of in silico predictions of protein-protein interactions using Comparative Docking Cockell, Simon J. Oliva, Baldo Jackson, Richard M. STRUCTURAL BIOINFORMATICS Motivation: Due to the limitations in experimental methods for determining binary interactions and structure determination of protein complexes, the need exists for computational models to fill the increasing gap between genome sequence information and protein annotation. Here we describe a novel method that uses structural models to reduce a large number of <it>in silico</it> predictions to a high confidence subset that is amenable to experimental validation. Results: A two-stage evaluation procedure was developed, first, a sequence-based method assessed the conservation of protein interface patches used in the original <it>in silico</it> prediction method, both in terms of position within the primary sequence, and in terms of sequence conservation. When applying the most stringent conditions it was found that 20.5% of the data set being assessed passed this test. Secondly, a high-throughput structure-based docking evaluation procedure assessed the soundness of three dimensional models produced for the putative interactions. Of the data set being assessed, 8264 interactions or over 70% could be modelled in this way, and 27% of these can be considered ‘valid’ by the applied criteria. In all, 6.9% of the interactions passed both the tests and can be considered to be a high confidence set of predicted interactions, several of which are described. Availability: <inter-ref locator="http://bioinformatics.leeds.ac.uk/~bmb4sjc" locator-type="url">http://bioinformatics.leeds.ac.uk/~bmb4sjc</inter-ref> Contact: <inter-ref locator="r.m.jackson@leeds.ac.uk" locator-type="email">r.m.jackson@leeds.ac.uk</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/573 http://dx.doi.org/10.1093/bioinformatics/btl661 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5892007-03-21HighWireOUPbioinfo:23:5

Automatic recognition and annotation of gene expression patterns of fly embryos Zhou, Jie Peng, Hanchuan GENE EXPRESSION Motivation: Gene expression patterns obtained by <it>in situ</it> mRNA hybridization provide important information about different genes during <it>Drosophila</it> embryogenesis. So far, annotations of these images are done by manually assigning a subset of anatomy ontology terms to an image. This time-consuming process depends heavily on the consistency of experts. Results: We develop a system to automatically annotate a fruitfly's embryonic tissue in which a gene has expression. We formulate the task as an image pattern recognition problem. For a new fly embryo image, our system answers two questions: (1) Which stage range does an image belong to? (2) Which annotations should be assigned to an image? We propose to identify the wavelet embryo features by multi-resolution 2D wavelet discrete transform, followed by min-redundancy max-relevance feature selection, which yields optimal distinguishing features for an annotation. We then construct a series of parallel bi-class predictors to solve the multi-objective annotation problem since each image may correspond to multiple annotations. Supplementary information: The complete annotation prediction results are available at: <inter-ref locator="http://www.cs.niu.edu/~jzhou/papers/fruitfly" locator-type="url">http://www.cs.niu.edu/~jzhou/papers/fruitfly</inter-ref> and <inter-ref locator="http://research.janelia.org/peng/proj/fly_embryo_annotation/" locator-type="url">http://research.janelia.org/peng/proj/fly_embryo_annotation/</inter-ref>. The datasets used in experiments will be available upon request to the correspondence author. Contact: <inter-ref locator="jzhou@cs.niu.edu" locator-type="email">jzhou@cs.niu.edu</inter-ref> and <inter-ref locator="pengh@janelia.hhmi.org" locator-type="email">pengh@janelia.hhmi.org</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/589 http://dx.doi.org/10.1093/bioinformatics/btl680 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/5632007-03-21HighWireOUPbioinfo:23:5

Molecular basis for specificity in the druggable kinome: sequence-based analysis Chen, Jianping Zhang, Xi Fernández, Ariel STRUCTURAL BIOINFORMATICS Motivation: Rational design of kinase inhibitors remains a challenge partly because there is no clear delineation of the molecular features that direct the pharmacological impact towards clinically relevant targets. Standard factors governing ligand affinity, such as potential for intermolecular hydrophobic interactions or for intermolecular hydrogen bonding do not provide good markers to assess cross reactivity. <it>Thus, a core question in the informatics of drug design is what type of molecular similarity among targets promotes promiscuity and what type of molecular difference governs specificity</it>. This work answers the question for a sizable screened sample of the human pharmacokinome including targets with unreported structure. Results: We show that drug design aimed at promoting pairwise interactions between ligand and kinase target actually fosters promiscuity because of the high conservation of the partner groups on or around the ATP-binding site of the kinase. Alternatively, we focus on a structural marker that may be reliably determined from sequence and measures dehydration propensities mostly localized on the loopy regions of kinases. Based on this marker, we construct a sequence-based kinase classifier that enables the accurate prediction of pharmacological differences. Our indicator is a microenvironmental descriptor that quantifies the propensity for water exclusion around preformed polar pairs. The results suggest that targeting polar dehydration patterns heralds a new generation of drugs that enable a tighter control of specificity than designs aimed at promoting ligand–kinase pairwise interactions. Availability: The predictor of polar hot spots for dehydration propensity, or solvent-accessible hydrogen bonds in soluble proteins, named YAPView, may be freely downloaded from the University of Chicago website <inter-ref locator="http://protlib.uchicago.edu/dloads.html" locator-type="url">http://protlib.uchicago.edu/dloads.html</inter-ref> Contact: <inter-ref locator="arifer@rice.edu" locator-type="email">arifer@rice.edu</inter-ref>, <inter-ref locator="ariel@uchicago.edu" locator-type="email">ariel@uchicago.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/563 http://dx.doi.org/10.1093/bioinformatics/btl666 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6482007-03-21HighWireOUPbioinfo:23:5

APOPTO-CELL--a simulation tool and interactive database for analyzing cellular susceptibility to apoptosis Huber, Heinrich J. Rehm, Markus Plchut, Martin Düssmann, Heiko Prehn, Jochen H. M. SYSTEMS BIOLOGY We have developed a web service that provides a comprehensive analysis of the susceptibility of cells to undergo apoptosis in response to an activation of the mitochondrial apoptotic pathway. Based on ordinary differential equations, (pre-determined) protein concentrations and release kinetics of mitochondrial pro-apoptotic factors, a network of 52 reactions and 19 reaction partners can be employed as a tool to display temporal protein profiles, to identify key regulatory proteins and to determine critical threshold concentrations required for the execution of apoptosis in HeLa cancer cells or other cell types. The web service also provides an interactive database function for the deposition of cell-type-specific quantitative data. In addition, the web service provides an output that can be compared directly to experimental results obtained from real-time single-cell experiments, making this a widely applicable systems biology tool for apoptosis and cancer researchers. Availability: <inter-ref locator="http://systemsbiology.rcsi.ie/apopto-cell.html" locator-type="url">http://systemsbiology.rcsi.ie/apopto-cell.html</inter-ref> Contact: <inter-ref locator="mrehm@rcsi.ie" locator-type="email">mrehm@rcsi.ie</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/648 http://dx.doi.org/10.1093/bioinformatics/btl684 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6312007-03-21HighWireOUPbioinfo:23:5

OMWSA: detection of DNA repeats using moving window spectral analysis Du, Liping Zhou, Hongxia Yan, Hong SEQUENCE ANALYSIS Summary: Repetitive DNA sequences play paramount biological roles, such as gene variation and regulatory functions on gene expressions. Until now, detection of various kinds of DNA repeats accurately is still an open problem. In this article, we propose a new method and a visualization tool for detecting DNA repeats in a 2D plane of location and frequency by using optimized moving window spectral analysis. The spectrogram can display the general distribution of repetitive sequences while showing the repeat period, length and location without any prior knowledge. Experimental results demonstrate that our method is accurate and robust even under the condition of excessive mutating and interleaving. Availability: Available on <inter-ref locator="http://www.hy8.com/~tec/sw01/omwsa01.zip" locator-type="url">http://www.hy8.com/~tec/sw01/omwsa01.zip</inter-ref>. Contact: <inter-ref locator="h.yan@cityu.edu.hk" locator-type="email">h.yan@cityu.edu.hk</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/631 http://dx.doi.org/10.1093/bioinformatics/btm008 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6512007-03-21HighWireOUPbioinfo:23:5

BioWeka--extending the Weka framework for bioinformatics Gewehr, Jan E. Szugat, Martin Zimmer, Ralf DATA AND TEXT MINING Summary: Given the growing amount of biological data, data mining methods have become an integral part of bioinformatics research. Unfortunately, standard data mining tools are often not sufficiently equipped for handling raw data such as e.g. amino acid sequences. One popular and freely available framework that contains many well-known data mining algorithms is the Waikato Environment for Knowledge Analysis (Weka). In the BioWeka project, we introduce various input formats for bioinformatics data and bioinformatics methods like alignments to Weka. This allows users to easily combine them with Weka's classification, clustering, validation and visualization facilities on a single platform and therefore reduces the overhead of converting data between different data formats as well as the need to write custom evaluation procedures that can deal with many different programs. We encourage users to participate in this project by adding their own components and data formats to BioWeka. Availability: The software, documentation and tutorial are available at <inter-ref locator="http://www.bioweka.org" locator-type="url">http://www.bioweka.org</inter-ref>. Contact: <inter-ref locator="support@bioweka.org" locator-type="email">support@bioweka.org</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/651 http://dx.doi.org/10.1093/bioinformatics/btl671 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6342007-03-21HighWireOUPbioinfo:23:5

DP-Bind: a web server for sequence-based prediction of DNA-binding residues in DNA-binding proteins Hwang, Seungwoo Gou, Zhenkun Kuznetsov, Igor B. SEQUENCE ANALYSIS Summary: This article describes DP-Bind, a web server for predicting DNA-binding sites in a DNA-binding protein from its amino acid sequence. The web server implements three machine learning methods: support vector machine, kernel logistic regression and penalized logistic regression. Prediction can be performed using either the input sequence alone or an automatically generated profile of evolutionary conservation of the input sequence in the form of PSI-BLAST position-specific scoring matrix (PSSM). PSSM-based kernel logistic regression achieves the accuracy of 77.2%, sensitivity of 76.4% and specificity of 76.6%. The outputs of all three individual methods are combined into a consensus prediction to help identify positions predicted with high level of confidence. Availability: Freely available at <inter-ref locator="http://lcg.rit.albany.edu/dp-bind" locator-type="url">http://lcg.rit.albany.edu/dp-bind</inter-ref> Contact: <inter-ref locator="IKuznetsov@albany.edu" locator-type="email">IKuznetsov@albany.edu</inter-ref> Supplementry information: <inter-ref locator="http://lcg.rit.albany.edu/dp-bind/dpbind_supplement.html" locator-type="url">http://lcg.rit.albany.edu/dp-bind/dpbind_supplement.html</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/634 http://dx.doi.org/10.1093/bioinformatics/btl672 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6392007-03-21HighWireOUPbioinfo:23:5

Software package for automatic microarray image analysis (MAIA) Novikov, Eugene Barillot, Emmanuel GENE EXPRESSION Summary: Although various software solutions are currently available for microarray image analysis, one would still expect to develop algorithms ensuring higher level of intelligence and robustness. We present a fully functional software package for automatic processing of the two-color microarray images including spot localization, quantification and quality control. The developed algorithms aim at making ratio estimates more resistant to array contamination and offer automatic tools to evaluate spot quality. Availability: A demo version of the software can be downloaded from <inter-ref locator="http://bioinfo.curie.fr/projects/maia" locator-type="url">http://bioinfo.curie.fr/projects/maia</inter-ref>. A full version is freely available to non-commercial users upon request from the authors. Contact: <inter-ref locator="eugene.novikov@curie.fr" locator-type="email">eugene.novikov@curie.fr</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/639 http://dx.doi.org/10.1093/bioinformatics/btl644 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6412007-03-21HighWireOUPbioinfo:23:5

R/qtlbim: QTL with Bayesian Interval Mapping in experimental crosses Yandell, Brian S. Mehta, Tapan Banerjee, Samprit Shriner, Daniel Venkataraman, Ramprasad Moon, Jee Young Neely, W. Whipple Wu, Hao von Smith, Randy Yi, Nengjun GENETICS AND POPULATION ANALYSIS Summary: R/qtlbim is an extensible, interactive environment for the Bayesian Interval Mapping of QTL, built on top of R/qtl (Broman <it>et al</it>., <cross-ref type="bib" refid="B3">2003</cross-ref>), providing Bayesian analysis of multiple interacting quantitative trait loci (QTL) models for continuous, binary and ordinal traits in experimental crosses. It includes several efficient Markov chain Monte Carlo (MCMC) algorithms for evaluating the posterior of genetic architectures, i.e. the number and locations of QTL, their main and epistatic effects and gene–environment interactions. R/qtlbim provides extensive informative graphical and numerical summaries, and model selection and convergence diagnostics of the MCMC output, illustrated through the vignette, example and demo capabilities of R (R Development Core Team <cross-ref type="bib" refid="B6">2006</cross-ref>). Availability: The package is freely available from <inter-ref locator="cran.r-project.org" locator-type="url">cran.r-project.org</inter-ref>. Contact: <inter-ref locator="byandell@wisc.edu" locator-type="email">byandell@wisc.edu</inter-ref> or <inter-ref locator="nyi@ms.soph.uab.edu" locator-type="email">nyi@ms.soph.uab.edu</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/641 http://dx.doi.org/10.1093/bioinformatics/btm011 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6542007-03-21HighWireOUPbioinfo:23:5

The ESID Online Database network Guzman, D. Veit, D. Knerr, V. Kindle, G. Gathmann, B. Eades-Perner, A. M. Grimbacher, B. DATABASES AND ONTOLOGIES Summary: Primary immunodeficiencies (PIDs) belong to the group of rare diseases. The European Society for Immunodeficiencies (ESID), is establishing an innovative European patient and research database network for continuous long-term documentation of patients, in order to improve the diagnosis, classification, prognosis and therapy of PIDs. The ESID Online Database is a web-based system aimed at data storage, data entry, reporting and the import of pre-existing data sources in an enterprise business-to-business integration (B2B). The online database is based on Java 2 Enterprise System (J2EE) with high-standard security features, which comply with data protection laws and the demands of a modern research platform. Availability: The ESID Online Database is accessible via the official website (<inter-ref locator="http://www.esid.org/" locator-type="url">http://www.esid.org/</inter-ref>). Contact: <inter-ref locator="b.grimbacher@medsch.ucl.ac.uk" locator-type="email">b.grimbacher@medsch.ucl.ac.uk</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/654 http://dx.doi.org/10.1093/bioinformatics/btl675 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/654-a2007-03-21HighWireOUPbioinfo:23:5

SNPassoc: an R package to perform whole genome association studies González, Juan R. Armengol, Lluís Solé, Xavier Guinó, Elisabet Mercader, Josep M. Estivill, Xavier Moreno, Víctor GENETICS AND POPULATION ANALYSIS Summary: The popularization of large-scale genotyping projects has led to the widespread adoption of genetic association studies as the tool of choice in the search for single nucleotide polymorphisms (SNPs) underlying susceptibility to complex diseases. Although the analysis of individual SNPs is a relatively trivial task, when the number is large and multiple genetic models need to be explored it becomes necessary a tool to automate the analyses. In order to address this issue, we developed SNPassoc, an R package to carry out most common analyses in whole genome association studies. These analyses include descriptive statistics and exploratory analysis of missing values, calculation of Hardy–Weinberg equilibrium, analysis of association based on generalized linear models (either for quantitative or binary traits), and analysis of multiple SNPs (haplotype and epistasis analysis). Availability: Package SNPassoc is available at CRAN from <inter-ref locator="http://cran.r-project.org" locator-type="url">http://cran.r-project.org</inter-ref> Contact: <inter-ref locator="juanramon.gonzalez@crg.es" locator-type="email">juanramon.gonzalez@crg.es</inter-ref> or <inter-ref locator="v.moreno@iconcologia.net" locator-type="email">v.moreno@iconcologia.net</inter-ref> Supplementary information: A tutorial is available on <it>Bioinformatics</it> online and in <inter-ref locator="http://davinci.crg.es/estivill_lab/snpassoc" locator-type="url">http://davinci.crg.es/estivill_lab/snpassoc</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/654-a http://dx.doi.org/10.1093/bioinformatics/btm025 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6372007-03-21HighWireOUPbioinfo:23:5

SMotif: a server for structural motifs in proteins Pugalenthi, Ganesan Suganthan, P. N. Sowdhamini, R. Chakrabarti, Saikat STRUCTURAL BIOINFORMATICS Summary: SMotif is a server that identifies important structural segments or motifs for a given protein structure(s) based on conservation of both sequential as well as important structural features such as solvent inaccessibility, secondary structural content, hydrogen bonding pattern and residue packing. This server also provides three-dimensional orientation patterns of the identified motifs in terms of inter-motif distances and torsion angles. These motifs may form the common core and therefore, can also be employed to design and rationalize protein engineering and folding experiments. Availability: SMotif server is available via the URL <inter-ref locator="http://caps.ncbs.res.in/SMotif/index.html" locator-type="url">http://caps.ncbs.res.in/SMotif/index.html</inter-ref>. Contact: <inter-ref locator="chakraba@mail.nih.gov" locator-type="email">chakraba@mail.nih.gov</inter-ref>, <inter-ref locator="mini@ncbs.res.in" locator-type="email">mini@ncbs.res.in</inter-ref> or <inter-ref locator="EPNSugan@ntu.edu.sg" locator-type="email">EPNSugan@ntu.edu.sg</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/637 http://dx.doi.org/10.1093/bioinformatics/btl679 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6292007-03-21HighWireOUPbioinfo:23:5

Compressed suffix tree--a basis for genome-scale sequence analysis Välimäki, Niko Gerlach, Wolfgang Dixit, Kashyap Mäkinen, Veli SEQUENCE ANALYSIS Summary: Suffix tree is one of the most fundamental data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length <it>n</it> from alphabet Σ = {<it>A</it>, <it>C</it>, <it>G</it>, <it>T</it> } can be stored in <it>n</it> log |Σ|= 2<it>n</it> bits, its suffix tree occupies <it>O</it>(<it>n</it> log <it>n</it>) bits. In practice, the size difference easily reaches factor 50. We provide an implementation of the <it>compressed suffix tree</it> very recently proposed by Sadakane (<it>Theory of Computing Systems</it>, in press). The compressed suffix tree occupies space proportional to the text size, i.e. <it>O</it>(<it>n</it> log} | Σ |) bits, and supports all typical suffix tree operations with at most log <it>n</it> factor slowdown. Our experiments show that, e.g. on a 10 MB DNA sequence, the compressed suffix tree takes 10% of the space of normal suffix tree. Typical operations are slowed down by factor 60. Availability: The C++ implementation under GNU license is available at <inter-ref locator="http://www.cs.helsinki.fi/group/suds/cst/" locator-type="url">http://www.cs.helsinki.fi/group/suds/cst/</inter-ref>. An example program implementing a typical pattern discovery task is included. Experimental results in this note correspond to version 0.95. Contact: <inter-ref locator="vmakinen@cs.helsinki.fi" locator-type="email">vmakinen@cs.helsinki.fi</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/629 http://dx.doi.org/10.1093/bioinformatics/btl681 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/5/6462007-03-21HighWireOUPbioinfo:23:5

SBaddon: high performance simulation for the Systems Biology Toolbox for MATLAB Schmidt, Henning SYSTEMS BIOLOGY Summary: We present the SBaddon package as an extension to the Systems Biology Toolbox for MATLAB (SBtoolbox). The goal of this extension is to provide the users of the SBtoolbox with important functionality that is needed for parameter estimation applications. While simulation in the SBtoolbox relies on the MATLAB ODE solvers, the SBaddon package provides considerably increased simulation performance through automatic generation of compiled simulation functions. Furthermore, the package contains improved optimization algorithms, forward parameter sensitivity analysis and basic numeric parameter identifiability analysis. Availability: The SBaddon package is open source and freely available for non-commercial use. Commercial use of SBaddon is only possible through a specific licensing agreement (contact <inter-ref locator="sbaddon@sbtoolbox.org" locator-type="email">sbaddon@sbtoolbox.org</inter-ref>). SBaddon can be obtained from <inter-ref locator="http://www.sbtoolbox.org/SBaddon" locator-type="url">http://www.sbtoolbox.org/SBaddon</inter-ref>. The website also contains extensive documentation, and examples. Contact: <inter-ref locator="henning@fcc.chalmers.se" locator-type="email">henning@fcc.chalmers.se</inter-ref> Oxford University Press 2007-03-21 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/5/646 http://dx.doi.org/10.1093/bioinformatics/btl668 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/11882007-05-28HighWireOUPbioinfo:23:10

GAPWM: a genetic algorithm method for optimizing a position weight matrix Li, Leping Liang, Yu Bass, Robert L. SEQUENCE ANALYSIS Motivation: Position weight matrices (PMWs) are simple models commonly used in motif-finding algorithms to identify short functional elements, such as <it>cis</it>-regulatory motifs, on genes. When few experimentally verified motifs are available, estimation of the PWM may be poor. The resultant PWM may not reliably discriminate a true motif from a false one. While experimentally identifying such motifs remains time-consuming and expensive, low-resolution binding data from techniques such as ChIP-on-chip and ChIP-PET have become available. We propose a novel but simple method to improve a poorly estimated PWM using ChIP data. Methodology: Starting from an existing PWM, a set of ChIP sequences, and a set of background sequences, our method, GAPWM, derives an improved PWM via a genetic algorithm that maximizes the area under the receiver operating characteristic (ROC) curve. GAPWM can easily incorporate prior information such as base conservation. We tested our method on two PMWs (Oct4/Sox2 and p53) using three recently published ChIP data sets (human Oct4, mouse Oct4 and human p53). Results: GAPWM substantially increased the sensitivity/specificity of a poorly estimated PWM and further improved the quality of a good PWM. Furthermore, it still functioned when the starting PWM contained a major error. The ROC performance of GAPWM compared favorably with that of MEME and others. With increasing availability of ChIP data, our method provides an alternative for obtaining high-quality PWMs for genome-wide identification of transcription factor binding sites. Availability: The C source code and all data used in this report are available at <inter-ref locator="http://dir.niehs.nih.gov/dirbb/gapwm" locator-type="url">http://dir.niehs.nih.gov/dirbb/gapwm</inter-ref> Contact: <inter-ref locator="li3@niehs.nih.gov" locator-type="email">li3@niehs.nih.gov</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1188 http://dx.doi.org/10.1093/bioinformatics/btm080 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/11812007-05-28HighWireOUPbioinfo:23:10

IMEx: Imperfect Microsatellite Extractor Mudunuri, Suresh B. Nagarajaram, Hampapathalu A. GENOME ANALYSIS Motivation: Microsatellites, also known as simple sequence repeats, are the tandem repeats of nucleotide motifs of the size 1–6 bp found in every genome known so far. Their importance in genomes is well known. Microsatellites are associated with various disease genes, have been used as molecular markers in linkage analysis and DNA fingerprinting studies, and also seem to play an important role in the genome evolution. Therefore, it is of importance to study distribution, enrichment and polymorphism of microsatellites in the genomes of interest. For this, the prerequisite is the availability of a computational tool for extraction of microsatellites (perfect as well as imperfect) and their related information from whole genome sequences. Examination of available tools revealed certain lacunae in them and prompted us to develop a new tool. Results: In order to efficiently screen genome sequences for microsatellites (perfect as well as imperfect), we developed a new tool called IMEx (Imperfect Microsatellite Extractor). IMEx uses simple string-matching algorithm with sliding window approach to screen DNA sequences for microsatellites and reports the motif, copy number, genomic location, nearby genes, mutational events and many other features useful for in-depth studies. IMEx is more sensitive, efficient and useful than the available widely used tools. IMEx is available in the form of a stand-alone program as well as in the form of a web-server. Availability: A World Wide Web server and the stand-alone program are available for free access at <inter-ref locator="http://203.197.254.154/IMEX/" locator-type="url">http://203.197.254.154/IMEX/</inter-ref> or <inter-ref locator="http://www.cdfd.org.in/imex" locator-type="url">http://www.cdfd.org.in/imex</inter-ref> Contact: <inter-ref locator="han@cdfd.org.in" locator-type="email">han@cdfd.org.in</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1181 http://dx.doi.org/10.1093/bioinformatics/btm097 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/11952007-05-28HighWireOUPbioinfo:23:10

A fast and flexible approach to oligonucleotide probe design for genomes and gene families Feng, Shengzhong Tillier, Elisabeth R.M. SEQUENCE ANALYSIS Motivation: With hundreds of completely sequenced microbial genomes available, and advancements in DNA microarray technology, the detection of genes in microbial communities consisting of hundreds of thousands of sequences may be possible. The existing strategies developed for DNA probe design, geared toward identifying specific sequences, are not suitable due to the lack of coverage, flexibility and efficiency necessary for applications in metagenomics. Methods: ProDesign is a tool developed for the selection of oligonucleotide probes to detect members of gene families present in environmental samples. Gene family-specific probe sequences are generated based on specific and shared words, which are found with the spaced seed hashing algorithm. To detect more sequences, those sharing some common words are re-clustered into new families, then probes specific for the new families are generated. Results: The program is very flexible in that it can be used for designing probes for detecting many genes families simultaneously and specifically in one or more genomes. Neither the length nor the melting temperature of the probes needs to be predefined. We have found that ProDesign provides more flexibility, coverage and speed than other software programs used in the selection of probes for genomic and gene family arrays. Availability: ProDesign is licensed free of charge to academic users. ProDesign and Supplementary Material can be obtained by contacting the authors. A web server for ProDesign is available at <inter-ref locator="http://www.uhnresearch.ca/labs/tillier/ProDesign/ProDesign.html" locator-type="url">http://www.uhnresearch.ca/labs/tillier/ProDesign/ProDesign.html</inter-ref> Contact: <inter-ref locator="e.tillier@utoronto.ca" locator-type="email">e.tillier@utoronto.ca</inter-ref> or <inter-ref locator="fsz@ncic.ac.cn" locator-type="email">fsz@ncic.ac.cn</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1195 http://dx.doi.org/10.1093/bioinformatics/btm114 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12032007-05-28HighWireOUPbioinfo:23:10

AutoSCOP: automated prediction of SCOP classifications using unique pattern-class mappings Gewehr, Jan E. Hintermair, Volker Zimmer, Ralf STRUCTURAL BIOINFORMATICS Motivation: The sequence patterns contained in the available motif and hidden Markov model (HMM) databases are a valuable source of information for protein sequence annotation. For structure prediction and fold recognition purposes, we computed mappings from such pattern databases to the protein domain hierarchy given by the ASTRAL compendium and applied them to the prediction of SCOP classifications. Our aim is to make highly confident predictions also for non-trivial cases if possible and abstain from a prediction otherwise, and thus to provide a method that can be used as a first step in a pipeline of prediction methods. We describe two successful examples for such pipelines. With the AutoSCOP approach, it is possible to make predictions in a large-scale manner for many domains of the available sequences in the well-known protein sequence databases. Results: AutoSCOP computes unique sequence patterns and pattern combinations for SCOP classifications. For instance, we assign a SCOP superfamily to a pattern found in its members whenever the pattern does not occur in any other SCOP superfamily. Especially on the fold and superfamily level, our method achieves both high sensitivity (above 93%) and high specificity (above 98%) on the difference set between two ASTRAL versions, due to being able to abstain from unreliable predictions. Further, on a harder test set filtered at low sequence identity, the combination with profile–profile alignments improves accuracy and performs comparably even to structure alignment methods. Integrating our method with structure alignment, we are able to achieve an accuracy of 99% on SCOP fold classifications on this set. In an analysis of false assignments of domains from new folds/superfamilies/families to existing SCOP classifications, AutoSCOP correctly abstains for more than 70% of the domains belonging to new folds and superfamilies, and more than 80% of the domains belonging to new families. These findings show that our approach is a useful additional filter for SCOP classification prediction of protein domains in combination with well-known methods such as profile–profile alignment. Availability: A web server where users can input their domain sequences is available at <inter-ref locator="http://www.bio.ifi.lmu.de/autoscop" locator-type="url">http://www.bio.ifi.lmu.de/autoscop</inter-ref> Contact: <inter-ref locator="jan.gewehr@ifi.lmu.de" locator-type="email">jan.gewehr@ifi.lmu.de</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1203 http://dx.doi.org/10.1093/bioinformatics/btm089 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12822007-05-28HighWireOUPbioinfo:23:10

UniRef: comprehensive and non-redundant UniProt reference clusters Suzek, Baris E. Huang, Hongzhan McGarvey, Peter Mazumder, Raja Wu, Cathy H. DATABASES AND ONTOLOGIES Motivation: Redundant protein sequences in biological databases hinder sequence similarity searches and make interpretation of search results difficult. Clustering of protein sequence space based on sequence similarity helps organize all sequences into manageable datasets and reduces sampling bias and overrepresentation of sequences. Results: The UniRef (UniProt Reference Clusters) provide clustered sets of sequences from the UniProt Knowledgebase (UniProtKB) and selected UniProt Archive records to obtain complete coverage of sequence space at several resolutions while hiding redundant sequences. Currently covering >4 million source sequences, the UniRef100 database combines identical sequences and subfragments from any source organism into a single UniRef entry. UniRef90 and UniRef50 are built by clustering UniRef100 sequences at the 90 or 50% sequence identity levels. UniRef100, UniRef90 and UniRef50 yield a database size reduction of ∼10, 40 and 70%, respectively, from the source sequence set. The reduced redundancy increases the speed of similarity searches and improves detection of distant relationships. UniRef entries contain summary cluster and membership information, including the sequence of a representative protein, member count and common taxonomy of the cluster, the accession numbers of all the merged entries and links to rich functional annotation in UniProtKB to facilitate biological discovery. UniRef has already been applied to broad research areas ranging from genome annotation to proteomics data analysis. Availability: UniRef is updated biweekly and is available for online search and retrieval at <inter-ref locator="http://www.uniprot.org" locator-type="url">http://www.uniprot.org</inter-ref>, as well as for download at <inter-ref locator="ftp://ftp.uniprot.org/pub/databases/uniprot/uniref" locator-type="url">ftp://ftp.uniprot.org/pub/databases/uniprot/uniref</inter-ref> Contact: <inter-ref locator="bes23@georgetown.edu" locator-type="email">bes23@georgetown.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1282 http://dx.doi.org/10.1093/bioinformatics/btm098 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12432007-05-28HighWireOUPbioinfo:23:10

A mixture model approach to the tests of concordance and discordance between two large-scale experiments with two-sample groups Lai, Yinglei Adam, Bao-ling Podolsky, Robert She, Jin-Xiong GENE EXPRESSION Motivation: Due to advances in experimental technologies, such as microarray, mass spectrometry and nuclear magnetic resonance, it is feasible to obtain large-scale data sets, in which measurements for a large number of features can be simultaneously collected. However, the sample sizes of these data sets are usually small due to their relatively high costs, which leads to the issue of concordance among different data sets collected for the same study: features should have consistent behavior in different data sets. There is a lack of rigorous statistical methods for evaluating this concordance or discordance. Methods: Based on a three-component normal-mixture model, we propose two likelihood ratio tests for evaluating the concordance and discordance between two large-scale data sets with two sample groups. The parameter estimation is achieved through the expectation-maximization (E-M) algorithm. A normal-distribution-quantile-based method is used for data transformation. Results: To evaluate the proposed tests, we conducted some simulation studies, which suggested their satisfactory performances. As applications, the proposed tests were applied to three SELDI-MS data sets with replicates. One data set has replicates from different platforms and the other two have replicates from the same platform. We found that data generated by SELDI-MS showed satisfactory concordance between replicates from the same platform but unsatisfactory concordance between replicates from different platforms. Availability: The R codes are freely available at <inter-ref locator="http://home.gwu.edu/~ylai/research/Concordance" locator-type="url">http://home.gwu.edu/~ylai/research/Concordance</inter-ref> Contact: <inter-ref locator="ylai@gwu.edu" locator-type="email">ylai@gwu.edu</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1243 http://dx.doi.org/10.1093/bioinformatics/btm103 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12172007-05-28HighWireOUPbioinfo:23:10

Pooling mRNA in microarray experiments and its effect on power Zhang, Wuyan Carriquiry, Alicia Nettleton, Dan Dekkers, Jack C.M. GENE EXPRESSION Motivation: Microarrays can simultaneously measure the expression levels of many genes and are widely applied to study complex biological problems at the genetic level. To contain costs, instead of obtaining a microarray on each individual, mRNA from several subjects can be first pooled and then measured with a single array. mRNA pooling is also necessary when there is not enough mRNA from each subject. Several studies have investigated the impact of pooling mRNA on inferences about gene expression, but have typically modeled the process of pooling as if it occurred in some transformed scale. This assumption is unrealistic. Results: We propose modeling the gene expression levels in a pool as a weighted average of mRNA expression of all individuals in the pool on the original measurement scale, where the weights correspond to individual sample contributions to the pool. Based on these improved statistical models, we develop the appropriate F statistics to test for differentially expressed genes. We present formulae to calculate the power of various statistical tests under different strategies for pooling mRNA and compare resulting power estimates to those that would be obtained by following the approach proposed by Kendziorski <it>et al</it>. (<cross-ref type="bib" refid="B5">2003</cross-ref>). We find that the Kendziorski estimate tends to exceed true power and that the estimate we propose, while somewhat conservative, is less biased. We argue that it is possible to design a study that includes mRNA pooling at a significantly reduced cost but with little loss of information. Contact: <inter-ref locator="alicia@iastate.edu" locator-type="email">alicia@iastate.edu</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1217 http://dx.doi.org/10.1093/bioinformatics/btm081 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12582007-05-28HighWireOUPbioinfo:23:10

Metabolic systems cost-benefit analysis for interpreting network structure and regulation Carlson, Ross P. SYSTEMS BIOLOGY Motivation: Interpretation of bioinformatics data in terms of cellular function is a major challenge facing systems biology. This question is complicated by robust metabolic networks filled with structural features like parallel pathways and isozymes. Under conditions of nutrient sufficiency, metabolic networks are well known to be regulated for thermodynamic efficiency however; efficient biochemical pathways are anabolically expensive to construct. While parameters like thermodynamic efficiency have been extensively studied, a systems-based analysis of anabolic proteome synthesis ‘costs’ and the cellular function implications of these costs has not been reported. Results: A cost-benefit analysis of an <it>in silico Escherichia coli</it> network revealed the relationship between metabolic pathway proteome synthesis requirements, DNA-coding sequence length, thermodynamic efficiency and substrate affinity. The results highlight basic metabolic network design principles. Pathway proteome synthesis requirements appear to have shaped biochemical network structure and regulation. Under conditions of nutrient scarcity and other general stresses, <it>E.coli</it> expresses pathways with relatively inexpensive proteome synthesis requirements instead of more efficient but also anabolically more expensive pathways. This evolutionary strategy provides a cellular function-based explanation for common network motifs like isozymes and parallel pathways and possibly explains ‘overflow’ metabolisms observed during nutrient scarcity. Contact: <inter-ref locator="alicia@iastate.edu" locator-type="email">alicia@iastate.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1258 http://dx.doi.org/10.1093/bioinformatics/btm082 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12512007-05-28HighWireOUPbioinfo:23:10

Modeling sequence-sequence interactions for drug response Lin, Min Li, Hongying Hou, Wei Johnson, Julie A. Wu, Rongling GENETICS AND POPULATION ANALYSIS Motivation: Genetic interactions or epistasis may play an important role in the genetic etiology of drug response. With the availability of large-scale, high-density single nucleotide polymorphism markers, a great challenge is how to associate haplotype structures and complex drug response through its underlying pharmacodynamic mechanisms. Results: We have derived a general statistical model for detecting an interactive network of DNA sequence variants that encode pharmacodynamic processes based on the haplotype map constructed by single nucleotide polymorphisms. The model was validated by a pharmacogenetic study for two predominant beta-adrenergic receptor (βAR) subtypes expressed in the heart, β1AR and β2AR. Haplotypes from these two receptors trigger significant interaction effects on the response of heart rate to different dose levels of dobutamine. This model will have implications for pharmacogenetic and pharmacogenomic research and drug discovery. Availability: A computer program written in Matlab can be downloaded from the webpage of statistical genetics group at the University of Florida. Contact: <inter-ref locator="rwu@mail.ifas.ufl.edu" locator-type="email">rwu@mail.ifas.ufl.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1251 http://dx.doi.org/10.1093/bioinformatics/btm110 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12352007-05-28HighWireOUPbioinfo:23:10

Using DNA microarrays to study gene expression in closely related species Oshlack, Alicia Chabot, Adrien E. Smyth, Gordon K. Gilad, Yoav GENE EXPRESSION Motivation: Comparisons of gene expression levels within and between species have become a central tool in the study of the genetic basis for phenotypic variation, as well as in the study of the evolution of gene regulation. DNA microarrays are a key technology that enables these studies. Currently, however, microarrays are only available for a small number of species. Thus, in order to study gene expression levels in species for which microarrays are not available, researchers face three sets of choices: (i) use a microarray designed for another species, but only compare gene expression levels within species, (ii) construct a new microarray for every species whose gene expression profiles will be compared or (iii) build a multi-species microarray with probes from each species of interest. Here, we use data collected using a multi-primate cDNA array to evaluate the reliability of each approach. Results: We find that, for inter-species comparisons, estimates of expression differences based on multi-species microarrays are more accurate than those based on multiple species-specific arrays. We also demonstrate that within-species expression differences can be estimated using a microarray for a closely related species, without discernible loss of information. Contact: A.O. (<inter-ref locator="oshlack@wehi.edu.au" locator-type="email">oshlack@wehi.edu.au</inter-ref>) or Y.G. (<inter-ref locator="gilad@uchicago.edu" locator-type="email">gilad@uchicago.edu</inter-ref>) Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1235 http://dx.doi.org/10.1093/bioinformatics/btm111 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12742007-05-28HighWireOUPbioinfo:23:10

A new method to measure the semantic similarity of GO terms Wang, James Z. Du, Zhidian Payattakool, Rapeeporn Yu, Philip S. Chen, Chin-Fu DATA AND TEXT MINING Motivation: Although controlled biochemical or biological vocabularies, such as Gene Ontology (GO) (<inter-ref locator="http://www.geneontology.org" locator-type="url">http://www.geneontology.org</inter-ref>), address the need for consistent descriptions of genes in different data sources, there is still no effective method to determine the functional similarities of genes based on gene annotation information from heterogeneous data sources. Results: To address this critical need, we proposed a novel method to encode a GO term's semantics (biological meanings) into a numeric value by aggregating the semantic contributions of their ancestor terms (including this specific term) in the GO graph and, in turn, designed an algorithm to measure the semantic similarity of GO terms. Based on the semantic similarities of GO terms used for gene annotation, we designed a new algorithm to measure the functional similarity of genes. The results of using our algorithm to measure the functional similarities of genes in pathways retrieved from the saccharomyces genome database (SGD), and the outcomes of clustering these genes based on the similarity values obtained by our algorithm are shown to be consistent with human perspectives. Furthermore, we developed a set of online tools for gene similarity measurement and knowledge discovery. Availability: The online tools are available at: <inter-ref locator="http://bioinformatics.clemson.edu/G-SESAME" locator-type="url">http://bioinformatics.clemson.edu/G-SESAME</inter-ref> Contact: <inter-ref locator="jzwang@cs.clemson.edu" locator-type="email">jzwang@cs.clemson.edu</inter-ref> Supplementary information: <inter-ref locator="http://bioinformatics.clemson.edu/Publication/Supplement/gsp.htm" locator-type="url">http://bioinformatics.clemson.edu/Publication/Supplement/gsp.htm</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1274 http://dx.doi.org/10.1093/bioinformatics/btm087 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12112007-05-28HighWireOUPbioinfo:23:10

Glycan classification with tree kernels Yamanishi, Yoshihiro Bach, Francis Vert, Jean-Philippe STRUCTURAL BIOINFORMATICS Motivation: Glycans are covalent assemblies of sugar that play crucial roles in many cellular processes. Recently, comprehensive data about the structure and function of glycans have been accumulated, therefore the need for methods and algorithms to analyze these data is growing fast. Results: This article presents novel methods for classifying glycans and detecting discriminative glycan motifs with support vector machines (SVM). We propose a new class of tree kernels to measure the similarity between glycans. These kernels are based on the comparison of tree substructures, and take into account several glycan features such as the sugar type, the sugar bound type or layer depth. The proposed methods are tested on their ability to classify human glycans into four blood components: leukemia cells, erythrocytes, plasma and serum. They are shown to outperform a previously published method. We also applied a feature selection approach to extract glycan motifs which are characteristic of each blood component. We confirmed that some leukemia-specific glycan motifs detected by our method corresponded to several results in the literature. Availability: Softwares are available upon request. Contact: <inter-ref locator="yoshi@kuicr.kyoto-u.ac.jp" locator-type="email">yoshi@kuicr.kyoto-u.ac.jp</inter-ref> Supplementary information: Datasets are available at the following website: <inter-ref locator="http://web.kuicr.kyoto-u.ac.jp/supp/yoshi/glycankernel/" locator-type="url">http://web.kuicr.kyoto-u.ac.jp/supp/yoshi/glycankernel/</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1211 http://dx.doi.org/10.1093/bioinformatics/btm090 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12892007-05-28HighWireOUPbioinfo:23:10

Enhancements and modifications of primer design program Primer3 Koressaar, Triinu Remm, Maido SEQUENCE ANALYSIS Summary: The determination of annealing temperature is a critical step in PCR design. This parameter is typically derived from the melting temperature of the PCR primers, so for successful PCR work it is important to determine the melting temperature of primer accurately. We introduced several enhancements in the widely used primer design program Primer3. The improvements include a formula for calculating melting temperature and a salt correction formula. Also, the new version can take into account the effects of divalent cations, which are included in most PCR buffers. Another modification enables using lowercase masked template sequences for primer design. Availability: Features described in this article have been implemented into the development code of Primer3 and will be available in future versions (version 1.1 and newer) of Primer3. Also, a modified version is compiled under the name of mPrimer3 which is distributed independently. The web-based version of mPrimer3 is available at <inter-ref locator="http://bioinfo.ebc.ee/mprimer3/" locator-type="url">http://bioinfo.ebc.ee/mprimer3/</inter-ref> and the binary code is freely downloadable from the URL <inter-ref locator="http://bioinfo.ebc.ee/download/" locator-type="url">http://bioinfo.ebc.ee/download/</inter-ref>. Contact: <inter-ref locator="maido.remm@ut.ee" locator-type="email">maido.remm@ut.ee</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1289 http://dx.doi.org/10.1093/bioinformatics/btm091 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12252007-05-28HighWireOUPbioinfo:23:10

Domain-enhanced analysis of microarray data using GO annotations Liu, Jiajun Hughes-Oliver, Jacqueline M. Menius, J. Alan GENE EXPRESSION Motivation: New biological systems technologies give scientists the ability to measure thousands of bio-molecules including genes, proteins, lipids and metabolites. We use domain knowledge, e.g. the Gene Ontology, to guide analysis of such data. By focusing on domain-aggregated results at, say the molecular function level, increased interpretability is available to biological scientists beyond what is possible if results are presented at the gene level. Results: We use a ‘top–down’ approach to perform domain aggregation by first combining gene expressions before testing for differentially expressed patterns. This is in contrast to the more standard ‘bottom–up’ approach, where genes are first tested individually then aggregated by domain knowledge. The benefits are greater sensitivity for detecting signals. Our method, domain-enhanced analysis (DEA) is assessed and compared to other methods using simulation studies and analysis of two publicly available leukemia data sets. Availability: Our DEA method uses functions available in R (<inter-ref locator="http://www.r-project.org/" locator-type="url">http://www.r-project.org/</inter-ref>) and SAS (<inter-ref locator="http://www.sas.com/" locator-type="url">http://www.sas.com/</inter-ref>). The two experimental data sets used in our analysis are available in R as Bioconductor packages, ‘ALL’ and ‘golubEsets’ (<inter-ref locator="http://www.bioconductor.org/" locator-type="url">http://www.bioconductor.org/</inter-ref>). Contact: <inter-ref locator="jliu6@stat.ncsu.edu" locator-type="email">jliu6@stat.ncsu.edu</inter-ref> Supplementary information: Supplementary data are available at <it>Bioinformatics</it> online. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1225 http://dx.doi.org/10.1093/bioinformatics/btm092 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12652007-05-28HighWireOUPbioinfo:23:10

The impact of function perturbations in Boolean networks Xiao, Yufei Dougherty, Edward R. SYSTEMS BIOLOGY Motivation: A network is said to be <it>robust</it> relative to a certain network characteristic if a small change in network structure does not significantly affect the characteristic. From the perspective of network stability, robustness is desirable; however, from the perspective of intervention to exert influence on network behavior, it is undesirable. For Boolean networks, there are two fundamental types of robustness. One type pertains to perturbing the state of the network and the other to perturbing the rule-based structure. Results: This article explores the impact of function perturbations in Boolean networks from two aspects: (1) analysis: predict the impact on network state transitions and attractors via analytical approaches or identify a perturbation by observing its consequences; (2) synthesis: preserve or modify the network characteristics, especially attractors, by introducing a judicious change to the functions. The results are applied to achieve intervention that structurally alters the network to achieve a more favorable steady-state distribution and to identify the function perturbation that has led to altered observed behavior. The intervention procedure is applied to a WNT5A network to reduce the risk of metastasis in melanoma, and the identification procedure is applied to a <it>Drosophila melanogaster</it> segmentation polarity gene network to identify regulatory function perturbation. Contact: <inter-ref locator="edward@ece.tamu.edu" locator-type="email">edward@ece.tamu.edu</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1265 http://dx.doi.org/10.1093/bioinformatics/btm093 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/13012007-05-28HighWireOUPbioinfo:23:10

BioGuideSRS: querying multiple sources with a user-centric perspective Cohen-Boulakia, Sarah Biton, Olivier Davidson, Susan Froidevaux, Christine DATABASES AND ONTOLOGIES Summary: Biologists are frequently faced with the problem of integrating information from multiple heterogeneous sources with their own experimental data. Given the large number of public sources, it is difficult to choose which sources to integrate without assistance. When doing this manually, biologists differ in their <it>preferences</it> concerning the sources to be queried as well as the <it>strategies</it>, i.e. the querying process they follow for navigating through the sources. In response to these findings, we have developed BioGuide to assist scientists search for relevant data within external sources while taking their preferences and strategies into account. In this article, we present BioGuideSRS, a user-friendly system which automatically retrieves instances of data by using BioGuide on top of the sequence retrieval system (SRS). BioGuideSRS is an Applet that can be run from its web page on any system with Java 5.0. Availability: <inter-ref locator="http://www.bioguide-project.net" locator-type="url">http://www.bioguide-project.net</inter-ref> Contact: <inter-ref locator="sarahcb@seas.upenn.edu" locator-type="email">sarahcb@seas.upenn.edu</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1301 http://dx.doi.org/10.1093/bioinformatics/btm088 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12922007-05-28HighWireOUPbioinfo:23:10

iPTREE-STAB: interpretable decision tree based method for predicting protein stability changes upon mutations Huang, Liang-Tsung Gromiha, M. Michael Ho, Shinn-Ying STRUCTURAL BIOINFORMATICS Summary: We have developed a web server, iPTREE-STAB for discriminating the stability of proteins (stabilizing or destabilizing) and predicting their stability changes (ΔΔG) upon single amino acid substitutions from amino acid sequence. The discrimination and prediction are mainly based on decision tree coupled with adaptive boosting algorithm, and classification and regression tree, respectively, using three neighboring residues of the mutant site along N- and C-terminals. Our method showed an accuracy of 82% for discriminating the stabilizing and destabilizing mutants, and a correlation of 0.70 for predicting protein stability changes upon mutations. Availability: <inter-ref locator="http://bioinformatics.myweb.hinet.net/iptree.htm" locator-type="url">http://bioinformatics.myweb.hinet.net/iptree.htm</inter-ref> Contact: <inter-ref locator="michael-gromiha@aist.go.jp" locator-type="email">michael-gromiha@aist.go.jp</inter-ref> Supplementary information: Dataset and other details are given. Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1292 http://dx.doi.org/10.1093/bioinformatics/btm100 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12972007-05-28HighWireOUPbioinfo:23:10

SBML export interface for the systems biology toolbox for MATLAB Schmidt, Hening Drews, Gunnar Vera, Julio Wolkenhauer, Olaf SYSTEMS BIOLOGY Summary: In this application note, we present an Systems biology markup language (SBML) export interface for the Systems Biology Toolbox for MATLAB. This interface allows modelers to automatically convert models, represented in the toolbox's own format (SBmodels) to SBML files. Since SBmodels do not explicitly contain all the information that is required to generate SBML, the necessary information is gathered by parsing SBmodels. The export can be done in two different ways. First, it is possible to call the export from the command line, thereby directly converting a model to an SBML file. The second option is to inspect and edit the conversion results with the help of a graphical user interface and to subsequently export the model to SBML. Availability: The SBML export interface has been integrated into the Systems Biology Toolbox for MATLAB, which is open source and freely available from <inter-ref locator="http://www.sbtoolbox.org" locator-type="url">http://www.sbtoolbox.org</inter-ref>. The website also contains a tutorial, extensive documentation and examples. Contact: <inter-ref locator="henning@fcc.chalmers.se" locator-type="email">henning@fcc.chalmers.se</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1297 http://dx.doi.org/10.1093/bioinformatics/btm105 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/13042007-05-28HighWireOUPbioinfo:23:10

Mediante: a web-based microarray data manager Le Brigand, Kevin Barbry, Pascal DATABASES AND ONTOLOGIES Summary: Mediante is a MIAME-compliant microarray data manager that links together annotations and experimental data. Developed as a J2EE three-tier application, Mediante integrates a management system for production of long oligonucleotide microarrays, an experimental data repository suitable for home made or commercial microarrays, and a user interface dedicated to the management of microarrays projects. Several tools allow quality control of hybridizations and submission of validated data to public repositories. Availability: <inter-ref locator="http://www.microarray.fr" locator-type="url">http://www.microarray.fr</inter-ref> Contact: <inter-ref locator="barbry@ipmc.cnrs.fr" locator-type="email">barbry@ipmc.cnrs.fr</inter-ref> or <inter-ref locator="lebrigand@ipmc.cnrs.fr" locator-type="email">lebrigand@ipmc.cnrs.fr</inter-ref> Supplementary information: <inter-ref locator="http://www.microarray.fr/SP/lebrigand2007/" locator-type="url">http://www.microarray.fr/SP/lebrigand2007/</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1304 http://dx.doi.org/10.1093/bioinformatics/btm106 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12992007-05-28HighWireOUPbioinfo:23:10

Cyclone: java-based querying and computing with Pathway/Genome databases Fèvre, François Le Smidtas, Serge Schächter, Vincent SYSTEMS BIOLOGY Summary: Cyclone aims at facilitating the use of BioCyc, a collection of Pathway/Genome Databases (PGDBs). Cyclone provides a fully extensible Java Object API to analyze and visualize these data. Cyclone can read and write PGDBs, and can write its own data in the CycloneML format. This format is automatically generated from the BioCyc ontology by Cyclone itself, ensuring continued compatibility. Cyclone objects can also be stored in a relational database CycloneDB. Queries can be written in SQL, and in an intuitive and concise object-oriented query language, Hibernate Query Language (HQL). In addition, Cyclone interfaces easily with Java software including the Eclipse IDE for HQL edition, the Jung API for graph algorithms or Cytoscape for graph visualization. Availability: Cyclone is freely available under an open source license at: <inter-ref locator="http://sourceforge.net/projects/nemo-cyclone" locator-type="url">http://sourceforge.net/projects/nemo-cyclone</inter-ref> Contact: <inter-ref locator="cyclone@genoscope.cns.fr" locator-type="email">cyclone@genoscope.cns.fr</inter-ref> Supplementary information: For download and installation instructions, tutorials, use cases and examples, see <inter-ref locator="http://nemo-cyclone.sourceforge.net" locator-type="url">http://nemo-cyclone.sourceforge.net</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1299 http://dx.doi.org/10.1093/bioinformatics/btm107 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/12942007-05-28HighWireOUPbioinfo:23:10

GenABEL: an R library for genome-wide association analysis Aulchenko, Yurii S. Ripke, Stephan Isaacs, Aaron van Duijn, Cornelia M. GENETICS AND POPULATION ANALYSIS Here we describe an R library for genome-wide association (GWA) analysis. It implements effective storage and handling of GWA data, fast procedures for genetic data quality control, testing of association of single nucleotide polymorphisms with binary or quantitative traits, visualization of results and also provides easy interfaces to standard statistical and graphical procedures implemented in base R and special R libraries for genetic analysis. We evaluated GenABEL using one simulated and two real data sets. We conclude that GenABEL enables the analysis of GWA data on desktop computers. Availability: <inter-ref locator="http://cran.r-project.org" locator-type="url">http://cran.r-project.org</inter-ref> Contact: <inter-ref locator="i.aoultchenko@erasmusmc.nl" locator-type="email">i.aoultchenko@erasmusmc.nl</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1294 http://dx.doi.org/10.1093/bioinformatics/btm108 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/10/13072007-05-28HighWireOUPbioinfo:23:10

DPTF: a database of poplar transcription factors Zhu, Qi-Hui Guo, An-Yuan Gao, Ge Zhong, Ying-Fu Xu, Meng Huang, Minren Luo, Jinchu DATABASES AND ONTOLOGIES Summary: The database of poplar transcription factors (DPTF) is a plant transcription factor (TF) database containing 2576 putative poplar TFs distributed in 64 families. These TFs were identified from both computational prediction and manual curation. We have provided extensive annotations including sequence features, functional domains, GO assignment and expression evidence for all TFs. In addition, DPTF contains cross-links to the <it>Arabidopsis</it> and rice transcription factor databases making it a unique resource for genome-scale comparative studies of transcriptional regulation in model plants. Availiability: DPTF is available at <inter-ref locator="http://dptf.cbi.pku.edu.cn" locator-type="url">http://dptf.cbi.pku.edu.cn</inter-ref> Contact: <inter-ref locator="dptf@mail.cbi.pku.edu.cn" locator-type="email">dptf@mail.cbi.pku.edu.cn</inter-ref> Oxford University Press 2007-05-28 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/10/1307 http://dx.doi.org/10.1093/bioinformatics/btm113 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e1912007-01-19HighWireOUPbioinfo:23:2

TOPP--the OpenMS proteomics pipeline Kohlbacher, Oliver Reinert, Knut Gröpl, Clemens Lange, Eva Pfeifer, Nico Schulz-Trieglaff, Ole Sturm, Marc ORIGINAL PAPERS Motivation: Experimental techniques in proteomics have seen rapid development over the last few years. Volume and complexity of the data have both been growing at a similar rate. Accordingly, data management and analysis are one of the major challenges in proteomics. Flexible algorithms are required to handle changing experimental setups and to assist in developing and validating new methods. In order to facilitate these studies, it would be desirable to have a flexible ‘toolbox’ of versatile and user-friendly applications allowing for rapid construction of computational workflows in proteomics. Results: We describe a set of tools for proteomics data analysis—TOPP, The OpenMS Proteomics Pipeline. TOPP provides a set of computational tools which can be easily combined into analysis pipelines even by non-experts and can be used in proteomics workflows. These applications range from useful utilities (file format conversion, peak picking) over wrapper applications for known applications (e.g. Mascot) to completely new algorithmic techniques for data reduction and data analysis. We anticipate that TOPP will greatly facilitate rapid prototyping of proteomics data evaluation pipelines. As such, we describe the basic concepts and the current abilities of TOPP and illustrate these concepts in the context of two example applications: the identification of peptides from a raw dataset through database search and the complex analysis of a standard addition experiment for the absolute quantitation of biomarkers. The latter example demonstrates TOPP's ability to construct flexible analysis pipelines in support of complex experimental setups. Availability: The TOPP components are available as open-source software under the lesser GNU public license (LGPL). Source code is available from the project website at <inter-ref locator="www.OpenMS.de" locator-type="url">www.OpenMS.de</inter-ref> Contact: <inter-ref locator="oliver.kohlbacher@uni-tuebingen.de" locator-type="email">oliver.kohlbacher@uni-tuebingen.de</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e191 http://dx.doi.org/10.1093/bioinformatics/btl299 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e1632007-01-19HighWireOUPbioinfo:23:2

Rediscovering secondary structures as network motifs--an unsupervised learning approach Raveh, Barak Rahat, Ofer Basri, Ronen Schreiber, Gideon ORIGINAL PAPERS Motivation: Secondary structures are key descriptors of a protein fold and its topology. In recent years, they facilitated intensive computational tasks for finding structural homologues, fold prediction and protein design. Their popularity stems from an appealing regularity in patterns of geometry and chemistry. However, the definition of secondary structures is of subjective nature. An unsupervised de-novo discovery of these structures would shed light on their nature, and improve the way we use these structures in algorithms of structural bioinformatics. Methods: We developed a new method for unsupervised partitioning of undirected graphs, based on patterns of small recurring network motifs. Our input was the network of all H-bonds and covalent interactions of protein backbones. This method can be also used for other biological and non-biological networks. Results: In a fully unsupervised manner, and without assuming any explicit prior knowledge, we were able to rediscover the existence of conventional α-helices, parallel β-sheets, anti-parallel sheets and loops, as well as various non-conventional hybrid structures. The relation between connectivity and crystallographic temperature factors establishes the existence of novel secondary structures. Contact: <inter-ref locator="barak.raveh@weizmann.ac.il" locator-type="email">barak.raveh@weizmann.ac.il</inter-ref>; <inter-ref locator="gideon.schreiber@weizmann.ac.il" locator-type="email">gideon.schreiber@weizmann.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e163 http://dx.doi.org/10.1093/bioinformatics/btl290 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e2252007-01-19HighWireOUPbioinfo:23:2

A tale of two tails: why are terminal residues of proteins exposed? Jacob, Etai Unger, Ron ORIGINAL PAPERS Motivation: It is widely known that terminal residues of proteins (i.e. the N- and C-termini) are predominantly located on the surface of proteins and exposed to the solvent. However, there is no good explanation as to the forces driving this phenomenon. The common explanation that terminal residues are charged, and charged residues prefer to be on the surface, cannot explain the magnitude of the phenomenon. Here, we survey a large number of proteins from the PDB in order to explore, quantitatively, this phenomenon, and then we use a lattice model to study the mechanisms involved. Results: The location of the termini was examined for 425 small monomeric proteins (50–200 amino acids) and it was found that the average solvent accessibility of termini residues is 87.1% compared with 49.2% of charged residues and 35.9% of all residues. Using a cutoff of 50% of the maximal possible exposure, 80.3% of the N-terminal and 86.1% of the C-terminal residues are exposed compared to 32% for all residues. In addition, terminal residues are much more distant from the center of mass of their proteins than other residues. Using a 2D lattice, a large population of model proteins was studied on three levels: structural selection of compact structures, thermodynamic selection of conformations with a pronounced energy gap and kinetic selection of fast folding proteins using Monte-Carlo simulations. Progressively, each selection raises the proportion of proteins with termini on the surface, resulting in similar proportions to those observed for real proteins. Contact: <inter-ref locator="ron@biocom1.ls.biu.ac.il" locator-type="email">ron@biocom1.ls.biu.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e225 http://dx.doi.org/10.1093/bioinformatics/btl318 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e1772007-01-19HighWireOUPbioinfo:23:2

Biological network comparison using graphlet degree distribution Przulj, Natasa ORIGINAL PAPERS Motivation: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in <it>all</it> of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. Results: We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes ‘touching’ <it>k</it> edges, into distributions measuring the number of nodes ‘touching’ <it>k graphlets</it>, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 <it>graphlet degree distributions</it> of graphlets with 2–5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network ‘agreement’ measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erdös–Rény, random scale-free, or Barabási–Albert scale-free networks. Availability: Software executables are available upon request. Contact: <inter-ref locator="natasha@ics.uci.edu" locator-type="email">natasha@ics.uci.edu</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e177 http://dx.doi.org/10.1093/bioinformatics/btl301 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e2122007-01-19HighWireOUPbioinfo:23:2

Prediction and simulation of motion in pairs of transmembrane {alpha}-helices Enosh, Angela Fleishman, Sarel J. Ben-Tal, Nir Halperin, Dan ORIGINAL PAPERS Motivation: Motion in transmembrane (TM) proteins plays an essential role in a variety of biological phenomena. Thus, developing an automated method for predicting and simulating motion in this class of proteins should result in an increased level of understanding of crucial physiological mechanisms. We have developed an algorithm for predicting and simulating motion in TM proteins of the α-helix bundle type. Our method employs probabilistic motion-planning techniques to suggest possible collision-free motion paths. The resulting paths are ranked according to the quality of the van der Waals interactions between the TM helices. Our algorithm considers a wide range of degrees of freedom (dofs) involved in the motion, including external and internal moves. However, in order to handle the vast dimensionality of the problem, we employ some constraints on these dofs in a way that is unlikely to rule out the native motion of the protein. Our algorithm simulates the motion, including all the dofs, and automatically produces a movie that demonstrates it. Results: Overexpression of the RTK ErbB2 was implicated in causing a variety of human cancers. Recently, a molecular mechanism for rotation-coupled activation of the receptor was suggested. We applied our algorithm to investigate the TM domain of this protein, and compared our results with this mechanism. A motion pathway that was similar to the proposed mechanism ranked first, and motions with partial overlap to this pathway followed in rank order. In addition, we conducted a negative-control computational-experiment using Glycophorin A. Our results confirmed the immobility of this TM protein, resulting in degenerate paths comprising native-like conformations. Supplementary information: Supplementary data are available at <inter-ref locator="http://www.cs.tau.ac.il/~angela/EGFR.html" locator-type="url">http://www.cs.tau.ac.il/~angela/EGFR.html</inter-ref> Contact: <inter-ref locator="angela@post.tau.ac.il" locator-type="email">angela@post.tau.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e212 http://dx.doi.org/10.1093/bioinformatics/btl325 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e1982007-01-19HighWireOUPbioinfo:23:2

Difference detection in LC-MS data for protein biomarker discovery Listgarten, Jennifer Neal, Radford M. Roweis, Sam T. Wong, Peter Emili, Andrew ORIGINAL PAPERS Motivation: There is a pressing need for improved proteomic screening methods allowing for earlier diagnosis of disease, systematic monitoring of physiological responses and the uncovering of fundamental mechanisms of drug action. The combined platform of LC-MS (Liquid-Chromatography-Mass-Spectrometry) has shown promise in moving toward a solution in these areas. In this paper we present atechnique for discovering differences in protein signal between two classes of samples of LC-MS serum proteomic data without use of tandem mass spectrometry, gels or labeling. This method works on data from a lower-precision MS instrument, the type routinely used by and available to the community at large today. We test our technique on a controlled (spike-in) but realistic (serum biomarker discovery) experiment which is therefore verifiable. We also develop a new method for helping to assess the difficulty of a given spike-in problem. Lastly, we show that the problem of class prediction, sometimes mistaken as a solution to biomarker discovery, is actually a much simpler problem. Results: Using precision–recall curves with experimentally extracted ground truth, we show that (1) our technique has good performance using seven replicates from each class, (2) performance degrades with decreasing number of replicates, (3) the signal that we are teasing out is not trivially available (i.e. the differences are not so large that the task is easy). Lastly, we easily obtain perfect classification results for data in which the problem of extracting differences does not produce absolutely perfect results. This emphasizes the different nature of the two problems and also their relative difficulties. Availability: Our data are publicly available as a benchmark for further studies of this nature at <inter-ref locator="http://www.cs.toronto.edu/~jenn/LCMS" locator-type="url">http://www.cs.toronto.edu/~jenn/LCMS</inter-ref> Supplementary Information: <inter-ref locator="http://www.cs.toronto.edu/~jennl/LCMS" locator-type="url">http://www.cs.toronto.edu/~jennl/LCMS</inter-ref> Contact: <inter-ref locator="jenn@cs.toronto.edu" locator-type="email">jenn@cs.toronto.edu</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e198 http://dx.doi.org/10.1093/bioinformatics/btl326 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e2052007-01-19HighWireOUPbioinfo:23:2

Vorolign--fast structural alignment using Voronoi contacts Birzele, Fabian Gewehr, Jan E. Csaba, Gergely Zimmer, Ralf ORIGINAL PAPERS Summary: Vorolign, a fast and flexible structural alignment method for two or more protein structures is introduced. The method aligns protein structures using double dynamic programming and measures the similarity of two residues based on the evolutionary conservation of their corresponding Voronoi-contacts in the protein structure. This similarity function allows aligning protein structures even in cases where structural flexibilities exist. Multiple structural alignments are generated from a set of pairwise alignments using a consistency-based, progressive multiple alignment strategy. Results: The performance of Vorolign is evaluated for different applications of protein structure comparison, including automatic family detection as well as pairwise and multiple structure alignment. Vorolign accurately detects the correct family, superfamily or fold of a protein with respect to the SCOP classification on a set of difficult target structures. A scan against a database of >4000 proteins takes on average 1 min per target. The performance of Vorolign in calculating pairwise and multiple alignments is found to be comparable with other pairwise and multiple protein structure alignment methods. Availability: Vorolign is freely available for academic users as a web server at <inter-ref locator="http://www.bio.ifi.lmu.de/Vorolign" locator-type="url">http://www.bio.ifi.lmu.de/Vorolign</inter-ref> Contact: <inter-ref locator="fabian.birzele@ifi.lmu.de" locator-type="email">fabian.birzele@ifi.lmu.de</inter-ref> Supplementary information: Datasets used throughout the article are available at <inter-ref locator="http://www.bio.ifi.lmu.de/Vorolign/supplement.html" locator-type="url">http://www.bio.ifi.lmu.de/Vorolign/supplement.html</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e205 http://dx.doi.org/10.1093/bioinformatics/btl294 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e1842007-01-19HighWireOUPbioinfo:23:2

Similarities and differences of gene expression in yeast stress conditions Rokhlenko, Oleg Wexler, Ydo Yakhini, Zohar ORIGINAL PAPERS Motivation and Methods: All living organisms and the survival of all cells critically depend on their ability to sense and quickly adapt to changes in the environment and to other stress conditions. We study stress response mechanisms in <it>Saccharomyces cerevisiae</it> by identifying genes that, according to very stringent criteria, have persistent co-expression under a variety of stress conditions. This is enabled through a fast clique search method applied to the intersection of several co-expression graphs calculated over the data of Gasch <it>et al</it>. This method exploits the topological characteristics of these graphs. Results: We observe cliques in the intersection graphs that are much larger than expected under a null model of changing gene identities for different stress conditions but maintaining the co-expression topology within each one. Persistent cliques are analyzed to identify enriched function as well as enriched regulation by a small number of TFs. These TFs, therefore, characterize a universal and persistent reaction to stress response. We further demonstrate that the vertices (genes) of many cliques in the intersection graphs are co-localized in the yeast genome, to a degree far beyond the random expectation. Co-localization can hypothetically contribute to a quick co-ordinated response. We propose the use of persistent cliques in further study of properties of co-regulation. Supplementary information: <inter-ref locator="http://www.cs.technion.ac.il/~olegro/stress.html" locator-type="url">http://www.cs.technion.ac.il/~olegro/stress.html</inter-ref> Contact: <inter-ref locator="olegro@cs.technion.ac.il" locator-type="email">olegro@cs.technion.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e184 http://dx.doi.org/10.1093/bioinformatics/btl308 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e1702007-01-19HighWireOUPbioinfo:23:2

Identification of conserved protein complexes based on a model of protein network evolution Hirsh, Eitan Sharan, Roded ORIGINAL PAPERS Motivation: Data on protein–protein interactions (PPIs) are increasing exponentially. To date, large-scale protein interaction networks are available for human and most model species. The arising challenge is to organize these networks into models of cellular machinery. As in other biological domains, a comparative approach provides a powerful basis for addressing this challenge. Results: We develop a probabilistic model for protein complexes that are conserved across two species. The model describes the evolution of conserved protein complexes from an ancestral species by protein interaction attachment and detachment and gene duplication events. We apply our model to search for conserved protein complexes within the PPI networks of yeast and fly, which are the largest networks in public databases. We detect 150 conserved complexes that match well-known complexes in yeast and are coherent in their functional annotations both in yeast and in fly. In comparison with two previous approaches, our model yields higher specificity and sensitivity levels in protein complex detection. Availability: The program is available upon request. Contact: <inter-ref locator="roded@tau.ac.il" locator-type="email">roded@tau.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e170 http://dx.doi.org/10.1093/bioinformatics/btl295 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e2192007-01-19HighWireOUPbioinfo:23:2

Using an alignment of fragment strings for comparing protein structures Friedberg, Iddo Harder, Tim Kolodny, Rachel Sitbon, Einat Li, Zhanwen Godzik, Adam ORIGINAL PAPERS Motivation: Most methods that are used to compare protein structures use three-dimensional (3D) structural information. At the same time, it has been shown that a 1D string representation of local protein structure retains a degree of structural information. This type of representation can be a powerful tool for protein structure comparison and classification, given the arsenal of sequence comparison tools developed by computational biology. However, in order to do so, there is a need to first understand how much information is contained in various possible 1D representations of protein structure. Results: Here we describe the use of a particular structure fragment library, denoted here as KL-strings, for the 1D representation of protein structure. Using KL-strings, we develop an infrastructure for comparing protein structures with a 1D representation. This study focuses on the added value gained from such a description. We show the new local structure language adds resolution to the traditional three-state (helix, strand and coil) secondary structure description, and provides a high degree of accuracy in recognizing structural similarities when used with a pairwise alignment benchmark. The results of this study have immediate applications towards fast structure recognition, and for fold prediction and classification. Contact: <inter-ref locator="idoerg@burnham.org" locator-type="email">idoerg@burnham.org</inter-ref> Supplementary information: <inter-ref locator="http://iddo-friedberg.org/" locator-type="url">http://iddo-friedberg.org/</inter-ref>ECCB06-supplement Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e219 http://dx.doi.org/10.1093/bioinformatics/btl310 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e172007-01-19HighWireOUPbioinfo:23:2

Incremental window-based protein sequence alignment algorithms Rangwala, Huzefa Karypis, George ORIGINAL PAPERS Motivation: Protein sequence alignment plays a critical role in computational biology as it is an integral part in many analysis tasks designed to solve problems in comparative genomics, structure and function prediction, and homology modeling. Methods: We have developed novel sequence alignment algorithms that compute the alignment between a pair of sequences based on short fixed- or variable-length high-scoring subsequences. Our algorithms build the alignments by repeatedly selecting the highest scoring pairs of subsequences and using them to construct small portions of the final alignment. We utilize PSI-BLAST generated sequence profiles and employ a profile-to-profile scoring scheme derived from PICASSO. Results: We evaluated the performance of the computed alignments on two recently published benchmark datasets and compared them against the alignments computed by existing state-of-the-art dynamic programming-based profile-to-profile local and global sequence alignment algorithms. Our results show that the new algorithms achieve alignments that are comparable with or better than those achieved by existing algorithms. Moreover, our results also showed that these algorithms can be used to provide better information as to which of the aligned positions are more reliable—a critical piece of information for comparative modeling applications. Contact: <inter-ref locator="rangwala@cs.umn.edu" locator-type="email">rangwala@cs.umn.edu</inter-ref> Supplementary information: <inter-ref locator="http://bioinfo.cs.umn.edu/supplements/win-aln/" locator-type="url">http://bioinfo.cs.umn.edu/supplements/win-aln/</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e17 http://dx.doi.org/10.1093/bioinformatics/btl297 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/1342007-01-19HighWireOUPbioinfo:23:2

Predicting transcription factor affinities to DNA from a biophysical model Roider, Helge G. Kanhere, Aditi Manke, Thomas Vingron, Martin GENOME ANALYSIS Motivation: Theoretical efforts to understand the regulation of gene expression are traditionally centered around the identification of transcription factor binding sites at specific DNA positions. More recently these efforts have been supplemented by experimental data for relative binding affinities of proteins to longer intergenic sequences. The question arises to what extent these two approaches converge. In this paper, we adopt a physical binding model to predict the relative binding affinity of a transcription factor for a given sequence. Results: We find that a significant fraction of genome-wide binding data in yeast can be accounted for by simple count matrices and a physical model with only two parameters. We demonstrate that our approach is both conceptually and practically more powerful than traditional methods, which require selection of a cutoff. Our analysis yields biologically meaningful parameters, suitable for predicting relative binding affinities in the absence of experimental binding data. Availability: The C source code for our TRAP program is freely available for non-commercial use at <inter-ref locator="http://www.molgen.mpg.de/~manke/papers/TFaffinities/" locator-type="url">http://www.molgen.mpg.de/~manke/papers/TFaffinities/</inter-ref> Contact: <inter-ref locator="vingron@molgen.mpg.de" locator-type="email">vingron@molgen.mpg.de</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/134 http://dx.doi.org/10.1093/bioinformatics/btl565 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/1422007-01-19HighWireOUPbioinfo:23:2

Reliable prediction of Drosha processing sites improves microRNA gene prediction Helvik, Snorre A. Snøve, Ola Sætrom, Pål GENOME ANALYSIS Motivation: Mature microRNAs (miRNAs) are processed from long hairpin transcripts. Even though it is only the first of several steps, the initial Drosha processing defines the mature product and is characteristic for all miRNA genes. Methods that can separate between true and false processing sites are therefore essential to miRNA gene discovery. Results: We present a classifier that predicts 5′ Drosha processing sites in hairpins that are candidate miRNAs. The classifier, called Microprocessor SVM, correctly predicts the processing site for 50% of known human 5′ miRNAs, and 90% of its predictions are within two nucleotides of the true site. Another classifier that is trained on the output from the Microprocessor SVM outperforms existing methods for prediction of unconserved miRNAs. Reanalysis of characteristics and supporting evidence for a set of newly annotated miRNAs shows that some miRNAs may be misannotated. This suggests that expressed hairpins should not be annotated as miRNAs until they are verified to be Drosha and Dicer substrates. Availability: The classifiers are publicly available at <inter-ref locator="https://demo1.interagon.com/miRNA/" locator-type="url">https://demo1.interagon.com/miRNA/</inter-ref> Contact: <inter-ref locator="paal.saetrom@interagon.com" locator-type="email">paal.saetrom@interagon.com</inter-ref> Supplementary information: Supplementary data is available at <it>Bioinformatics</it> online. Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/142 http://dx.doi.org/10.1093/bioinformatics/btl570 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/1332007-01-19HighWireOUPbioinfo:23:2

EDITORIAL Valencia, Alfonso Bateman, Alex Executive Editors, EDITORIALS Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/133 http://dx.doi.org/10.1093/bioinformatics/btl635 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e992007-01-19HighWireOUPbioinfo:23:2

Electrostatic potentials of proteins in water: a structured continuum approach Hildebrandt, Andreas Blossey, Ralf Rjasanow, Sergej Kohlbacher, Oliver Lenhof, Hans-Peter ORIGINAL PAPERS Electrostatic interactions play a crucial role in many biomolecular processes, including molecular recognition and binding. Biomolecular electrostatics is modulated to a large extent by the water surrounding the molecules. Here, we present a novel approach to the computation of electrostatic potentials which allows the inclusion of water structure into the classical theory of continuum electrostatics. Based on our recent purely differential formulation of nonlocal electrostatics [<cross-ref type="bib" refid="b8">Hildebrandt, <it>et al.</it> (2004)</cross-ref> <it>Phys. Rev. Lett</it>., 93, 108104] we have developed a new algorithm for its efficient numerical solution. The key component of this algorithm is a boundary element solver, having the same computational complexity as established boundary element methods for local continuum electrostatics. This allows, for the first time, the computation of electrostatic potentials and interactions of large biomolecular systems immersed in water including effects of the solvent's structure in a continuum description. We illustrate the applicability of our approach with two examples, the enzymes trypsin and acetylcholinesterase. The approach is applicable to all problems requiring precise prediction of electrostatic interactions in water, such as protein–ligand and protein–protein docking, folding and chromatin regulation. Initial results indicate that this approach may shed new light on biomolecular electrostatics and on aspects of molecular recognition that classical local electrostatics cannot reveal. Contact: <inter-ref locator="anhi@bioinf.uni-sb.de" locator-type="email">anhi@bioinf.uni-sb.de</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e99 http://dx.doi.org/10.1093/bioinformatics/btl312 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e712007-01-19HighWireOUPbioinfo:23:2

Family relationships: should consensus reign?--consensus clustering for protein families Nikolski, Macha Sherman, David J. ORIGINAL PAPERS Motivation: Reliable identification of protein families is key to phylogenetic analysis, functional annotation and the exploration of protein function diversity in a given phylogenetic branch. As more and more complete genomes are sequenced, there is a need for powerful and reliable algorithms facilitating protein families construction. Results: We have formulated the problem of protein families construction as an instance of consensus clustering, for which we designed a novel algorithm that is computationally efficient in practice and produces high quality results. Our algorithm uses an election method to construct consensus families from competing clustering computations. Our consensus clustering algorithm is tailored to serve the specific needs of comparative genomics projects. First, it provides a robust means to incorporate results from different and complementary clustering methods, thus avoiding the need for an a priori choice that may introduce computational bias in the results. Second, it is suited to large-scale projects due to the practical efficiency. And third, it produces high quality results where families tend to represent groupings by biological function. Availability: This method has been used for Génolevures project to compute protein families of Hemiascomycetous yeasts. The data are available online at <inter-ref locator="http://cbi.labri.fr/Genolevures/fam/" locator-type="url">http://cbi.labri.fr/Genolevures/fam/</inter-ref> Supplementary information: Supplementary data are available at <inter-ref locator="http://cbi.labri.fr/Genolevures/fam/" locator-type="url">http://cbi.labri.fr/Genolevures/fam/</inter-ref> Contact: <inter-ref locator="macha@labri.fr" locator-type="email">macha@labri.fr</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e71 http://dx.doi.org/10.1093/bioinformatics/btl314 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e842007-01-19HighWireOUPbioinfo:23:2

Discovering tightly regulated and differentially expressed gene sets in whole genome expression data Ye, Chun Eskin, Eleazar ORIGINAL PAPERS Motivation: Recently, a new type of expression data is being collected which aims to measure the effect of genetic variation on gene expression in pathways. In these datasets, expression profiles are constructed for multiple strains of the same model organism under the same condition. The goal of analyses of these data is to find differences in regulatory patterns due to genetic variation between strains, often without a phenotype of interest in mind. We present a new method based on notions of tight regulation and differential expression to look for sets of genes which appear to be significantly affected by genetic variation. Results: When we use categorical phenotype information, as in the Alzheimer's and diabetes datasets, our method finds many of the same gene sets as gene set enrichment analysis. In addition, our notion of correlated gene sets allows us to focus our efforts on biological processes subjected to tight regulation. In murine hematopoietic stem cells, we are able to discover significant gene sets independent of a phenotype of interest. Some of these gene sets are associated with several blood-related phenotypes. Availability: The programs are available by request from the authors. Contact: <inter-ref locator="cye@bioinf.ucsd.edu" locator-type="email">cye@bioinf.ucsd.edu</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e84 http://dx.doi.org/10.1093/bioinformatics/btl315 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e52007-01-19HighWireOUPbioinfo:23:2

Simulating multiplexed SNP discovery rates using base-specific cleavage and mass spectrometry Böcker, Sebastian ORIGINAL PAPERS Motivation: Single Nucleotide Polymorphisms (SNPs) are believed to contribute strongly to the genetic variability in living beings, and SNP and mutation discovery are of great interest in today's Life Sciences. A comparatively new method to discover such polymorphisms is based on base-specific cleavage, where resulting cleavage products are analyzed by mass spectrometry (MS). One particular advantage of this method is the possibility of multiplexing the biochemical reactions, i.e. examining multiple genomic regions in parallel. Simulations can help estimating the performance of a method for polymorphism discovery, and allow us to evaluate the influence of method parameters on the discovery rate, and also to investigate whether the method is well suited for a certain genomic region. Results: We show how to efficiently conduct such simulations for polymorphism discovery using base-specific cleavage and MS. Simulating multiplexed polymorphism discovery leads us to the problem of uniformly drawing a multiplex. Given a multiset of natural numbers we want to uniformly draw a subset of fixed cardinality so that the elements sum up to some fixed total length. We show how to enumerate multiplex layouts using dynamic programming, which allows us to uniformly draw a multiplex. Contact: <inter-ref locator="boecker@minet.uni-jena.de" locator-type="email">boecker@minet.uni-jena.de</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e5 http://dx.doi.org/10.1093/bioinformatics/btl291 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e772007-01-19HighWireOUPbioinfo:23:2

Optimization of probe coverage for high-resolution oligonucleotide aCGH Lipson, Doron Yakhini, Zohar Aumann, Yonatan ORIGINAL PAPERS Motivation: The resolution at which genomic alterations can be mapped by means of oligonucleotide aCGH (array-based comparative genomic hybridization) is limited by two factors: the availability of high-quality probes for the target genomic sequence and the array real-estate. Optimization of the probe selection process is required for arrays that are designed to probe specific genomic regions in very high resolution without compromising probe quality constraints. Results: In this paper we describe a well-defined optimization problem associated with the problem of probe selection for high-resolution aCGH arrays. We propose the whenever possible ∈-cover as a formulation that faithfully captures the requirement of probe selection problem, and provide a fast randomized algorithm that solves the optimization problem in <it>O</it>(<it>n</it> log<it>n</it>) time, as well as a deterministic algorithm with the same asymptotic performance. We apply the method in a typical high-definition array design scenario and demonstrate its superiority with respect to alternative approaches. Availability: Address requests to the authors. Contact: <inter-ref locator="dlipson@cs.technion.ac.il" locator-type="email">dlipson@cs.technion.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e77 http://dx.doi.org/10.1093/bioinformatics/btl316 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e2372007-01-19HighWireOUPbioinfo:23:2

EBIMed--text crunching to gather facts for proteins from Medline Rebholz-Schuhmann, Dietrich Kirsch, Harald Arregui, Miguel Gaudan, Sylvain Riethoven, Mark Stoehr, Peter ORIGINAL PAPERS Summary: To allow efficient and systematic retrieval of statements from Medline we have developed EBIMed, a service that combines document retrieval with co-occurrence-based analysis of Medline abstracts. Upon keyword query, EBIMed retrieves the abstracts from EMBL-EBI's installation of Medline and filters for sentences that contain biomedical terminology maintained in public bioinformatics resources. The extracted sentences and terminology are used to generate an overview table on proteins, Gene Ontology (GO) annotations, drugs and species used in the same biological context. All terms in retrieved abstracts and extracted sentences are linked to their entries in biomedical databases. We assessed the quality of the identification of terms and relations in the retrieved sentences. More than 90% of the protein names found indeed represented a protein. According to the analysis of four protein–protein pairs from the Wnt pathway we estimated that 37% of the statements containing such a pair mentioned a meaningful interaction and clarified the interaction of Dkk with LRP. We conclude that EBIMed improves access to information where proteins and drugs are involved in the same biological process, e.g. statements with GO annotations of proteins, protein–protein interactions and effects of drugs on proteins. Availability: Available at <inter-ref locator="http://www.ebi.ac.uk/Rebholz-srv/ebimed" locator-type="url">http://www.ebi.ac.uk/Rebholz-srv/ebimed</inter-ref> Supplementary Data: Supplementary Data are available at <it>Bioinformatics</it> online. Contact: <inter-ref locator="Rebholz@ebi.ac.uk" locator-type="email">Rebholz@ebi.ac.uk</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e237 http://dx.doi.org/10.1093/bioinformatics/btl302 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e442007-01-19HighWireOUPbioinfo:23:2

Simultaneous alignment and annotation of cis-regulatory regions Bais, Abha Singh Grossmann, Steffen Vingron, Martin ORIGINAL PAPERS Motivation: Current methods that annotate conserved transcription factor binding sites in an alignment of two regulatory regions perform the alignment and annotation step separately and combine the results in the end. If the site descriptions are weak or the sequence similarity is low, the local gap structure of the alignment poses a problem in detecting the conserved sites. It is therefore desirable to have an approach that is able to simultaneously consider the alignment as well as possibly matching site locations. Results: With SimAnn we have developed a tool that serves exactly this purpose. By combining the annotation step and the alignment of the two sequences into one algorithm, it detects conserved sites more clearly. It has the additional advantage that all parameters are calculated based on statistical considerations. This allows for its successful application with any binding site model of interest. We present the algorithm and the approach for parameter selection and compare its performance with that of other, non-simultaneous methods on both simulated and real data. Availability: A command-line based C++ implementation of SimAnn is available from the authors upon request. In addition, we provide Perl scripts for calculating the input parameters based on statistical considerations. Contact: <inter-ref locator="bais@molgen.mpg.de" locator-type="email">bais@molgen.mpg.de</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e44 http://dx.doi.org/10.1093/bioinformatics/btl305 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e2312007-01-19HighWireOUPbioinfo:23:2

A novel pattern recognition algorithm to classify membrane protein unfolding pathways with high-throughput single-molecule force spectroscopy Marsico, Annalisa Labudde, Dirk Sapra, Tanuj Muller, Daniel J. Schroeder, Michael ORIGINAL PAPERS Motivation: Misfolding of membrane proteins plays an important role in many human diseases such as <it>retinitis pigmentosa</it>, hereditary deafness and <it>diabetes insipidus</it>. Little is known about membrane proteins as there are only very few high-resolution structures. Single-molecule force spectroscopy is a novel technique, which measures the force necessary to pull a protein out of a membrane. Such force curves contain valuable information on the protein structure, conformation, and inter- and intra-molecular forces. High-throughput force spectroscopy experiments generate hundreds of force curves including spurious ones and good curves, which correspond to different unfolding pathways. Manual analysis of these data is a bottleneck and source of inconsistent and subjective annotation. Results: We propose a novel algorithm for the identification of spurious curves and curves representing different unfolding pathways. Our algorithm proceeds in three stages: first, we reduce noise in the curves by applying dimension reduction; second, we align the curves with dynamic programming and compute pairwise distances and third, we cluster the curves based on these distances. We apply our method to a hand-curated dataset of 135 force curves of bacteriorhodopsin mutant P50A. Our algorithm achieves a success rate of 81% distinguishing spurious from good curves and a success rate of 76% classifying unfolding pathways. As a result, we discuss five different unfolding pathways of bacteriorhodopsin including three main unfolding events and several minor ones. Finally, we link folding barriers to the degree of conservation of residues. Overall, the algorithm tackles the force spectroscopy bottleneck and leads to more consistent and reproducible results paving the way for high-throughput analysis of structural features of membrane proteins. Contact: <inter-ref locator="annalisa.marsico@biotec.tu-dresden.de" locator-type="email">annalisa.marsico@biotec.tu-dresden.de</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e231 http://dx.doi.org/10.1093/bioinformatics/btl293 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e572007-01-19HighWireOUPbioinfo:23:2

Genetic code symmetry and efficient design of GC-constrained coding sequences Gavish, Matan Peled, Amnon Chor, Benny ORIGINAL PAPERS Motivation: Cloning of long DNA sequences (40–60 bases) into phage display libraries using polymerase chain reaction (PCR) is a low efficiency process, in which PCR is used to incorporate a DNA insert, coding for a certain peptide, into the amplified sequence. The PCR efficiency in this process is strongly affected by the distribution of G–C bases in the amplified sequence. As any DNA insert coding for the target peptide may be attempted, there is a flexibility in choosing part of the amplified sequence. Since the number of inserts coding for the same peptide is exponential in the peptide length, a computational problem naturally arises—that of efficiently finding an insert, whose parameters are optimal for PCR cloning. Results: The GC distribution requirements are formulated as a search problem. We developed an efficient, linear time ‘one pass’ algorithm for this problem. Interestingly, our algorithm strongly relies on an interesting symmetry, which we observed in the standard genetic code. Most non-standard genetic codes examined possess this symmetry as well, yet some do not. We generalize the search problem and consider the case of a non-standard, or arbitrary, genetic code where this symmetry does not necessary hold. We solve the generalized problem in polynomial, but nonlinear, time. Availability: An implementation of the proposed algorithm is available upon request from the authors. Contact: <inter-ref locator="benny@cs.tau.ac.il" locator-type="email">benny@cs.tau.ac.il</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e57 http://dx.doi.org/10.1093/bioinformatics/btl317 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e642007-01-19HighWireOUPbioinfo:23:2

Merging microarray cell synchronization experiments through curve alignment Hermans, Filip Tsiporkova, Elena ORIGINAL PAPERS Motivation: The validity of periodic cell cycle regulation studies in plants is seriously compromised by the relatively poor quality of cell synchrony that is achieved for plant suspension cultures in comparison to yeast and mammals. The present state-of-the-art plant synchronization techniques cannot offer a complete cell cycle coverage and moreover a considerable loss of cell synchrony may occur toward the end of the sampling. One possible solution is to consider combining multiple datasets, produced by different synchronization techniques and thus covering different phases of the cell cycle, in order to arrive at a better cell cycle coverage. Results: We propose a method that enables pasting expression profiles from different plant cell synchronization experiments and results in an expression curve that spans more than one cell cycle. The optimal pasting overlap is determined via a dynamic time warping alignment. Consequently, the different expression time series are merged together by aggregating the corresponding expression values lying within the overlap area. We demonstrate that the periodic analysis of the merged expression profiles produces more reliable <it>p</it>-values for periodicity. Subsequent Gene Ontology analysis of the results confirms that merging synchronization experiments is a more robust strategy for the selection of potentially periodic genes. Additional validation of the proposed algorithm on yeast data is also presented. Availability: Results, benchmark sets and scripts are freely available at our website: <inter-ref locator="http://www.psb.ugent.be/cbd/publications.php" locator-type="url">http://www.psb.ugent.be/cbd/publications.php</inter-ref> Contact: <inter-ref locator="elena.tsiporkova@ugent.be" locator-type="email">elena.tsiporkova@ugent.be</inter-ref>, <inter-ref locator="fiher@psb.ugent.be" locator-type="email">fiher@psb.ugent.be</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e64 http://dx.doi.org/10.1093/bioinformatics/btl320 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e502007-01-19HighWireOUPbioinfo:23:2

A comparative genome approach to marker ordering Faraut, T. de Givry, S. Chabrier, P. Derrien, T. Galibert, F. Hitte, C. Schiex, T. ORIGINAL PAPERS Motivation: Genome maps are fundamental to the study of an organism and essential in the process of genome sequencing which in turn provides the ultimate map of the genome. The increased number of genomes being sequenced offers new opportunities for the mapping of closely related organisms. We propose here an algorithmic formalization of a genome comparison approach to marker ordering. Results: In order to integrate a comparative mapping approach in the algorithmic process of map construction and selection, we propose to extend the usual statistical model describing the experimental data, here radiation hybrids (RH) data, in a statistical framework that models additionally the evolutionary relationships between a proposed map and a reference map: an existing map of the corresponding orthologous genes or markers in a closely related organism. This has concretely the effect of exploiting, in the process of map selection, the information of marker adjacencies in the related genome when the information provided by the experimental data is not conclusive for the purpose of ordering. In order to compute efficiently the map, we proceed to a reduction of the maximum likelihood estimation to the Traveling Salesman Problem. Experiments on simulated RH datasets as well as on a real RH dataset from the canine RH project show that maps produced using the likelihood defined by the new model are significantly better than maps built using the traditional RH model. Availability: The comparative mapping approach is available in the last version of de Givry,S. <it>et al</it>. [(2004) <it>Bioinformatics</it>, 21, 1703–1704, <inter-ref locator="www.inra.fr/mia/T/CarthaGene" locator-type="url">www.inra.fr/mia/T/CarthaGene</inter-ref>], a free (the LKH part is free for academic use only) mapping software in C++, including LKH (Helsgaun,K. (2000) <it>Eur. J. Oper. Res</it>., 126, 106–130, <inter-ref locator="www.dat.ruc.dk/keld/research/LKH" locator-type="url">www.dat.ruc.dk/keld/research/LKH</inter-ref>) for maximum likelihood computation. Contact: <inter-ref locator="thomas.faraut@toulouse.inra.fr" locator-type="email">thomas.faraut@toulouse.inra.fr</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e50 http://dx.doi.org/10.1093/bioinformatics/btl321 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e302007-01-19HighWireOUPbioinfo:23:2

Tandem repeats over the edit distance Sokol, Dina Benson, Gary Tojeira, Justin ORIGINAL PAPERS Motivation: A tandem repeat in DNA is a sequence of two or more contiguous, approximate copies of a pattern of nucleotides. Tandem repeats occur in the genomes of both eukaryotic and prokaryotic organisms. They are important in numerous fields including disease diagnosis, mapping studies, human identity testing (DNA fingerprinting), sequence homology and population studies. Although tandem repeats have been used by biologists for many years, there are few tools available for performing an exhaustive search for all tandem repeats in a given sequence. Results: In this paper we describe an efficient algorithm for finding all tandem repeats within a sequence, under the edit distance measure. The contributions of this paper are two-fold: theoretical and practical. We present a precise definition for tandem repeats over the edit distance and an efficient, deterministic algorithm for finding these repeats. Availability: The algorithm has been implemented in C++, and the software is available upon request and can be used at <inter-ref locator="http://www.sci.brooklyn.cuny.edu/~sokol/trepeats" locator-type="url">http://www.sci.brooklyn.cuny.edu/~sokol/trepeats</inter-ref>. The use of this tool will assist biologists in discovering new ways that tandem repeats affect both the structure and function of DNA and protein molecules. Contact: <inter-ref locator="sokol@sci.brooklyn.cuny.edu" locator-type="email">sokol@sci.brooklyn.cuny.edu</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e30 http://dx.doi.org/10.1093/bioinformatics/btl309 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e362007-01-19HighWireOUPbioinfo:23:2

Designing patterns for profile HMM search Sun, Yanni Buhler, Jeremy ORIGINAL PAPERS Motivation: Profile HMMs are a powerful tool for modeling conserved motifs in proteins. These models are widely used by search tools to classify new protein sequences into families based on domain architecture. However, the proliferation of known motifs and new proteomic sequence data poses a computational challenge for search, requiring days of CPU time to annotate an organism's proteome. Results: We use PROSITE-like patterns as a filter to speed up the comparison between protein sequence and profile HMM. A set of patterns is designed starting from the HMM, and only sequences matching one of these patterns are compared to the HMM by full dynamic programming. We give an algorithm to design patterns with maximal sensitivity subject to a bound on the false positive rate. Experiments show that our patterns typically retain at least 90% of the sensitivity of the source HMM while accelerating search by an order of magnitude. Availability: Contact the first author at the address below. Contact: <inter-ref locator="yanni@cse.wustl.edu" locator-type="email">yanni@cse.wustl.edu</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e36 http://dx.doi.org/10.1093/bioinformatics/btl323 en Copyright (C) 2007, Oxford University Press

oai:open-archive.highwire.org:bioinfo:23/2/e242007-01-19HighWireOUPbioinfo:23:2

Multiple alignment by sequence annealing S. Schwartz, Ariel Pachter, Lior ORIGINAL PAPERS Motivation: We introduce a novel approach to multiple alignment that is based on an algorithm for rapidly checking whether single matches are consistent with a partial multiple alignment. This leads to a <it>sequence annealing</it> algorithm, which is an incremental method for building multiple sequence alignments one match at a time. Our approach improves significantly on the standard progressive alignment approach to multiple alignment. Results: The sequence annealing algorithm performs well on benchmark test sets of protein sequences. It is not only sensitive, but also specific, drastically reducing the number of incorrectly aligned residues in comparison to other programs. The method allows for adjustment of the sensitivity/specificity tradeoff and can be used to reliably identify homologous regions among protein sequences. Availability: An implementation of the sequence annealing algorithm is available at <inter-ref locator="http://bio.math.berkeley.edu/amap/" locator-type="url">http://bio.math.berkeley.edu/amap/</inter-ref> Contact: <inter-ref locator="sariel@cs.berkeley.edu" locator-type="email">sariel@cs.berkeley.edu</inter-ref> Oxford University Press 2007-01-19 TEXT text/html http://bioinformatics.oxfordjournals.org/cgi/content/short/23/2/e24 http://dx.doi.org/10.1093/bioinformatics/btl311 en Copyright (C) 2007, Oxford University Press 1258784928457!0001-01-01!9999-12-31!bioinfo:23!100!oai_dc