bluuebunny/crossref_metadata_2025 huggingface dataset:
Low drive voltage Fabry-Pérot étalon device tunable filters using poled hybrid sol-gel materials
Authors: Gan Haiyong , Zhang Hongxi , DeRose Christopher T. , Norwood Robert A. , Peyghambarian Nasser , Fallahi Mahmoud , Luo Jingdong , Chen Baoquan , Jen Alex K.-Y.
Published: July 2006

Nonlinear optical chromophore coupled hybrid sol-gel materials have been synthesized and incorporated in Fabry-Pérot étalon devices (ED’s) using highly reflective distributed Bragg reflector mirrors. Étalon structures with indium tin oxide electrodes outside the ED cavity have been applied to reduce absorptive loss. Large tunability (∼0.75nm∕V), high finesse (∼235), and wide tunable range (>50nm) have been obtained. A transmitted light intensity isolation ratio of ∼35dB at ∼1550nm has been achieved at a low drive voltage of 10V. The electro-optic effect and inverse piezoelectric effect are discussed. The results indicate that such hybrid sol-gel ED’s are promising candidates for tunable filters in wavelength division multiplexing communication systems.
Isotopic effect in deuterium-induced semiconductor surface metallization: D∕3C–SiC(100) 3×2
Authors: Roy J. , Aristov V. Yu. , Radtke C. , Jaffrennou P. , Enriquez H. , Soukiassian P. , Moras P. , Spezzani C. , Crotti C. , Perfetti P.
Published: July 2006

Atomic deuterium (D) interaction with the polar 3C–SiC(100) 3×2 surface is investigated by synchrotron radiation-based valence band and core level photoemission. D is found to induce metallization of the surface. The D atoms lead to a charge transfer into the topmost Si and C planes, with D atoms terminating top surface dangling bond and an asymmetric attack in the third Si plane. However, a significant isotopic effect is observed when compared to the H-induced metallization with amazingly smaller charge transfer suggesting dynamical effects.
Narrow-band and broad-band polarization conversion reflection filters
Authors: Jen Yi-Jun , Peng Cheng-Yu
Published: July 2006

This work presents a simple method to enhance polarization conversion reflection from an anisotropic thin film. The total reflection effect at the interface of an anisotropic thin film causes strong e-ray and o-ray couplings, leading to enhanced polarization conversion. Arranging high-refraction thin film or low-refraction thin film in the prism/anisotropic thin film/air system yields narrowband or broadband polarization conversion reflection.
Electron field emission from TiO2 nanotube arrays synthesized by hydrothermal reaction
Authors: Miyauchi Masahiro , Tokudome Hiromasa , Toda Yoshitake , Kamiya Toshio , Hosono Hideo
Published: July 2006

Conductive TiO2 nanotube arrays were grown on metal Ti substrates by hydrothermal reaction and subsequent postannealing in vacuum. The nanotubes were vertically grown and adhered well to the substrates. The crystal structure of the postannealed TiO2 nanotubes was identified to be oxygen-defective anatase. The nanotube arrays exhibited efficient electron field emission even at room temperature with rather low turn-on fields ∼280V per electrode distance of 100μm. The emission current density exceeded 0.15mA∕cm2 at an extraction voltage of 800V. The emission current was reproducible and stable in the lower voltage (<800V) region.
Proportional and nonproportional transfer of movement sequences
Authors: Wilde Heather , Shea Charles H.
Published: July 2006

Two experiments were designed to determine participants’ ability to transfer a learned movement sequence to new spatial locations. A 16-element dynamic arm movement sequence was used in both experiments. The task required participants to move a horizontal lever to sequentially projected targets. Experiment 1 included 2 groups. One group practised a pattern in which targets were located at 20, 40, 60, and 80° from the start position (long sequence). The other group practised a pattern with targets at 20, 26.67, 60, and 80° (mixed sequence). Both groups were tested 24 hours later on the long, mixed, and short sequence. The short sequence was considered a proportional transfer for the long acquisition group because all the amplitudes between targets were reduced by the same proportion. Nonproportional transfer occurred when the amplitudes between targets did not have the same proportions as those for their practice sequence (e.g., long sequence to mixed sequence or vice versa). The results indicated that participants could effectively transfer to new target configurations regardless of whether the transfer required proportional or nonproportional spatial changes to the movement pattern. Experiment 2 assessed the effects of extended practice on proportional and nonproportional spatial transfer. The data indicated that while participants can effectively transfer to both proportional and nonproportional spatial transfer conditions after 1 day of practice, they are only effective at transferring to proportional transfer conditions after 4 days of practice. The results are discussed in terms of the mechanism by which response sequences become increasingly specific over extended practice in an attempt to optimize movement production.
MAA-1, a Novel Acyl-CoA–binding Protein Involved in Endosomal Vesicle Transport inCaenorhabditis elegans
Authors: Larsen Morten K. , Tuck Simon , Færgeman Nils J. , Knudsen Jens
Published: July 2006

The budding and fission of vesicles during membrane trafficking requires many proteins, including those that coat the vesicles, adaptor proteins that recruit components of the coat, and small GTPases that initiate vesicle formation. In addition, vesicle formation in vitro is promoted by the hydrolysis of acyl-CoA lipid esters. The mechanisms by which these lipid esters are directed to the appropriate membranes in vivo, and their precise roles in vesicle biogenesis, are not yet understood. Here, we present the first report on membrane associated ACBP domain-containing protein-1 (MAA-1), a novel membrane-associated member of the acyl-CoA–binding protein family. We show that in Caenorhabditis elegans, MAA-1 localizes to intracellular membrane organelles in the secretory and endocytic pathway and that mutations in maa-1 reduce the rate of endosomal recycling. A lack of maa-1 activity causes a change in endosomal morphology. Although in wild type, many endosomal organelles have long tubular protrusions, loss of MAA-1 activity results in loss of the tubular domains, suggesting the maa-1 is required for the generation or maintenance of these domains. Furthermore, we demonstrate that MAA-1 binds fatty acyl-CoA in vitro and that this ligand-binding ability is important for its function in vivo. Our results are consistent with a role for MAA-1 in an acyl-CoA–dependent process during vesicle formation.
Interpreting anonymous DNA samples from mass disasters—probabilistic forensic inference using genetic markers
Authors: Lin Tien-ho , Myers Eugene W. , Xing Eric P.
Published: July 2006

Motivation: The problem of identifying victims in a mass disaster using DNA fingerprints involves a scale of computation that requires efficient and accurate algorithms. In a typical scenario there are hundreds of samples taken from remains that must be matched to the pedigrees of the alleged victim’s surviving relatives. Moreover the samples are often degraded due to heat and exposure. To develop a competent method for this type of forensic inference problem, the complicated quality issues of DNA typing need to be handled appropriately, the matches between every sample and every family must be considered, and the confidence of matches need to be provided.

Results: We present a unified probabilistic framework that efficiently clusters samples, conservatively eliminates implausible sample-pedigree pairings, and handles both degraded samples (missing values) and experimental errors in producing and/or reading a genotype. We present a method that confidently exclude forensically unambiguous sample-family matches from the large hypothesis space of candidate matches, based on posterior probabilistic inference. Due to the high confidentiality of disaster DNA data, simulation experiments are commonly performed and used here for validation. Our framework is shown to be robust to these errors at levels typical in real applications. Furthermore, the flexibility in the probabilistic models makes it possible to extend this framework to include other biological factors such as interdependent markers, mitochondrial sequences, and blood type.

Availability: The software and data sets are available from the authors upon request.

Contact:  epxing@cs.cmu.edu
Finding the evidence for protein-protein interactions from PubMed abstracts
Authors: Jang Hyunchul , Lim Jaesoo , Lim Joon-Ho , Park Soo-Jun , Lee Kyu-Chul , Park Seon-Hee
Published: July 2006

Motivation: Protein-protein interactions play critical roles in biological processes, and many biologists try to find or to predict crucial information concerning these interactions. Before verifying interactions in biological laboratory work, validating them from previous research is necessary. Although many efforts have been made to create databases that store verified information in a structured form, much interaction information still remains as unstructured text. As the amount of new publications has increased rapidly, a large amount of research has sought to extract interactions from the text automatically. However, there remain various difficulties associated with the process of applying automatically generated results into manually annotated databases. For interactions that are not found in manually stored databases, researchers attempt to search for abstracts or full papers.

Results: As a result of a search for two proteins, PubMed frequently returns hundreds of abstracts. In this paper, a method is introduced that validates protein-protein interactions from PubMed abstracts. A query is generated from two given proteins automatically and abstracts are then collected from PubMed. Following this, target proteins and their synonyms are recognized and their interaction information is extracted from the collection. It was found that 67.37% of the interactions from DIP-PPI corpus were found from the PubMed abstracts and 87.37% of interactions were found from the given full texts.

Availability: Contact authors.

Contact:  janghc@etri.re.kr
springScape: visualisation of microarray and contextual bioinformatic data using spring embedding and an ‘information landscape’
Authors: Ebbels Timothy M. D. , Buxton Bernard F. , Jones David T.
Published: July 2006

The interpretation of microarray and other high-throughput data is highly dependent on the biological context of experiments. However, standard analysis packages are poor at simultaneously presenting both the array and related bioinformatic data. We have addressed this challenge by developing a system springScape based on ‘spring embedding’ and an ‘information landscape’ allowing several related data sources to be dynamically combined while highlighting one particular feature.

Each data source is represented as a network of nodes connected by weighted edges. The networks are combined and embedded in the 2-D plane by spring embedding such that nodes with a high similarity are drawn close together. Complex relationships can be discovered by varying the weight of each data source and observing the dynamic response of the spring network. By modifying Procrustes analysis, we find that the visualizations have an acceptable degree of reproducibility. The ‘information landscape’ highlights one particular data source, displaying it as a smooth surface whose height is proportional to both the information being viewed and the density of nodes. The algorithm is demonstrated using several microarray data sets in combination with protein-protein interaction data and GO annotations. Among the features revealed are the spatio-temporal profile of gene expression and the identification of GO terms correlated with gene expression and protein interactions. The power of this combined display lies in its interactive feedback and exploitation of human visual pattern recognition. Overall, springScape shows promise as a tool for the interpretation of microarray data in the context of relevant bioinformatic information.

Contact:  d.jones@cs.ucl.ac.uk

Supplementary information: Supplementary data are available at Bioinformatics online.
A combinatorial pattern discovery approach for the prediction of membrane dipping (re-entrant) loops
Authors: Lasso Gorka , Antoniw John F. , Mullins Jonathan G.L.
Published: July 2006

Motivation: Membrane dipping loops are sections of membrane proteins that reside in the membrane but do not traverse from one side to the other, rather they enter and leave the same side of the membrane. We applied a combinatorial pattern discovery approach to sets of sequences containing at least one characterised structure described as possessing a membrane dipping loop. Discovered patterns were found to be composed of residues whose biochemical role is known to be essential for function of the protein, thus validating our approach.

TMLOOP () was implemented to predict membrane dipping loops in polytopic membrane proteins. TMLOOP applies discovered patterns as weighted predictive rules in a collective motif method (a variation of the single motif method), to avoid inherent limitations of single motif methods in detecting distantly related proteins. The collective motif method applies several, partially overlapping patterns, which pertain to the same sequence region, allowing proteins containing small variations to be detected. The approach achieved 92.4% accuracy in sensitivity and 100% reliability in specificity. TMLOOP was applied to the Swiss-Prot database, identifying 1392 confirmed membrane dipping loops, 75 plausible membrane dipping loops hitherto uncharacterised by topology prediction methods or experimental approaches and 128 false positives (8.0%).

Contact:  j.g.l.mullins@swansea.ac.uk
Novel Unsupervised Feature Filtering of Biological Data
Authors: Varshavsky Roy , Gottlieb Assaf , Linial Michal , Horn David
Published: July 2006

Motivation: Many methods have been developed for selecting small informative feature subsets in large noisy data. However, unsupervised methods are scarce. Examples are using the variance of data collected for each feature, or the projection of the feature on the first principal component. We propose a novel unsupervised criterion, based on SVD-entropy, selecting a feature according to its contribution to the entropy (CE) calculated on a leave-one-out basis. This can be implemented in four ways: simple ranking according to CE values (SR); forward selection by accumulating features according to which set produces highest entropy (FS1); forward selection by accumulating features through the choice of the best CE out of the remaining ones (FS2); backward elimination (BE) of features with the lowest CE.

Results: We apply our methods to different benchmarks. In each case we evaluate the success of clustering the data in the selected feature spaces, by measuring Jaccard scores with respect to known classifications. We demonstrate that feature filtering according to CE outperforms the variance method and gene-shaving. There are cases where the analysis, based on a small set of selected features, outperforms the best score reported when all information was used. Our method calls for an optimal size of the relevant feature set. This turns out to be just a few percents of the number of genes in the two Leukemia datasets that we have analyzed. Moreover, the most favored selected genes turn out to have significant GO enrichment in relevant cellular processes.

Abbreviations: Singular Value Decomposition (SVD), Principal Component Analysis (PCA), Quantum Clustering (QC), Gene Shaving (GS), Variance Selection (VS), Backward Elimination (BE)

Contact:  royke@cs.huji.ac.il

Conflicts of Interest: not reported
Comparative footprinting of DNA-binding proteins
Authors: Contreras-Moreira Bruno , Collado-Vides Julio
Published: July 2006

Motivation: Comparative modelling is a computational method used to tackle a variety of problems in molecular biology and biotechnology. Traditionally it has been applied to model the structure of proteins on their own or bound to small ligands, although more recently it has also been used to model protein-protein interfaces. This work is the first to systematically analyze whether comparative models of protein-DNA complexes could be built and be useful for predicting DNA binding sites.

Results: First, we describe the structural and evolutionary conservation of protein-DNA interfaces, and the limits they impose on modelling accuracy. Second, we find that side-chains from contacting residues can be reasonably modeled and therefore used to identify contacting nucleotides. Third, the DNASITE protocol is implemented and different parameters are benchmarked on a set of 85 regulators from Escherichia coli. Results show that comparative footprinting can make useful predictions based solely on structural data, depending primarily on the interface identity with respect to the template used.

Availability: DNASITE code available on request from the authors

Contact:  contrera@ccg.unam.mx

Supplementary information:
DynaPred: A structure and sequence based method for the prediction of MHC class I binding peptide sequences and conformations
Authors: Antes Iris , Siu Shirley W. I. , Lengauer Thomas
Published: July 2006

Motivation: The binding of endogenous antigenic peptides to MHC class I molecules is an important step during the immunologic response of a host against a pathogen. Thus, various sequence- and structure-based prediction methods have been proposed for this purpose. The sequence-based methods are computationally efficient, but are hampered by the need of sufficient experimental data and do not provide a structural interpretation of their results. The structural methods are data-independent, but are quite time-consuming and thus not suited for screening of whole genomes. Here, we present a new method, which performs sequence-based prediction by incorporating information obtained from molecular modeling. This allows us to perform large databases screening and to provide structural information of the results.

Results: We developed a SVM-trained, quantitative matrix-based method for the prediction of MHC class I binding peptides, in which the features of the scoring matrix are energy terms retrieved from molecular dynamics simulations. At the same time we used the equilibrated structures obtained from the same simulations in a simple and efficient docking procedure. Our method consists of two steps: First, we predict potential binders from sequence data alone and second, we construct protein-peptide complexes for the predicted binders. So far, we tested our approach on the HLA-A0201 allele. We constructed two prediction models, using local, position-dependent (DynaPredPOS) and global, position-independent (DynaPred) features. The former model outperformed the two sequence-based methods used in our evaluation; the latter shows a much higher generalizability towards other alleles than the position-dependent models. The constructed peptide structures can be refined within seconds to structures with an average backbone RMSD of 1.53 Å from the corresponding experimental structures.

Contact:  antes@mpi-sb.mpg.de
An experimental metagenome data management and analysis system
Authors: Markowitz Victor M. , Ivanova Natalia , Palaniappan Krishna , Szeto Ernest , Korzeniewski Frank , Lykidis Athanasios , Anderson Iain , Mavrommatis Konstantinos , Kunin Victor , Garcia Martin Hector , Dubchak Inna , Hugenholtz Phil , Kyrpides Nikos C.
Published: July 2006

The application of shotgun sequencing to environmental samples has revealed a new universe of microbial community genomes (metagenomes) involving previously uncultured organisms. Metagenome analysis, which is expected to provide a comprehensive picture of the gene functions and metabolic capacity for microbial communities, needs to be conducted in the context of a comprehensive data management and analysis system. We present in this paper IMG/M, an experimental metagenome data management and analysis system that is based on the Integrated Microbial Genomes (IMG) system. IMG/M provides tools and viewers for analyzing both metagenomes and isolate genomes individually or in a comparative context. IMG/M is available at .

Contact:  vmmarkowitz@lbl.gov
The iRMSD: a local measure of sequence alignment accuracy using structural information
Authors: Armougom Fabrice , Moretti Sébastien , Keduas Vladimir , Notredame Cedric
Published: July 2006

Motivation: We introduce the iRMSD, a new type of RMSD, independent from any structure superposition and suitable for evaluating sequence alignments of proteins with known structures.

Results: We demonstrate that the iRMSD is equivalent to the standard RMSD although much simpler to compute and we also show that it is suitable for comparing sequence alignments and benchmarking multiple sequence alignment methods. We tested the iRMSD score on 6 established multiple sequence alignment packages and found the results to be consistent with those obtained using an established reference alignment collection like Prefab.

Availability: The iRMSD is part of the T-Coffee package and is distributed as an open source freeware ().

Contact:  cedric.notredame@europe.com; cedric.notredame@igs.cnrs-mrs.fr
Statistical mechanical modeling of genome-wide transcription factor occupancy data by MatrixREDUCE
Authors: Foat Barrett C. , Morozov Alexandre V. , Bussemaker Harmen J.
Published: July 2006

Motivation: Regulation of gene expression by a transcription factor requires physical interaction between the factor and the DNA, which can be described by a statistical mechanical model. Based on this model, we developed the MatrixREDUCE algorithm, which uses genome-wide occupancy data for a transcription factor (e.g. ChIP-chip) and associated nucleotide sequences to discover the sequence-specific binding affinity of the transcription factor. Advantages of our approach are that the information for all probes on the microarray is efficiently utilized because there is no need to delineate “bound” and “unbound” sequences, and that, unlike information content-based methods, it does not require a background sequence model.

Results: We validated the performance of MatrixREDUCE by inferring the sequence-specific binding affinities for several transcription factors in S. cerevisiae and comparing the results with three other independent sources of transcription factor sequence-specific affinity information: (i) experimental measurement of transcription factor binding affinities for specific oligonucleotides, (ii) reporter gene assays for promoters with systematically mutated binding sites, and (iii) relative binding affinities obtained by modeling transcription factor-DNA interactions based on co-crystal structures of transcription factors bound to DNA substrates. We show that transcription factor binding affinities inferred by MatrixREDUCE are in good agreement with all three validating methods.

Availability: MatrixREDUCE source code is freely available for non-commercial use at . The software runs on Linux, Unix, and Mac OS X.

Contact:  Harmen.Bussemaker@columbia.edu
On counting position weight matrix matches in a sequence, with application to discriminative motif finding
Authors: Sinha Saurabh
Published: July 2006

Motivation and Results: The position weight matrix (PWM) is a popular method to model transcription factor binding sites. A fundamental problem in cis-regulatory analysis is to “count” the occurrences of a PWM in a DNA sequence. We propose a novel probabilistic score to solve this problem of counting PWM occurrences. The proposed score has two important properties: (1) It gives appropriate weights to both strong and weak occurrences of the PWM, without using thresholds. (2) For any given PWM, this score can be computed while allowing for occurrences of other, a priori known PWMs, in a statistically sound framework. Additionally, the score is efficiently differentiable with respect to the PWM parameters, which has important consequences for designing search algorithms.

The second problem we address is to find, ab initio, PWMs that have high counts in one set of sequences, and low counts in another. We develop a novel algorithm to solve this “discriminative motif-finding problem”, using the proposed score for counting a PWM in the sequences. The algorithm is a local search technique that exploits derivative information on an objective function to enhance speed and performance. It is extensively tested on synthetic data, and shown to perform better than other discriminative as well as non-discriminative PWM finding algorithms. It is then applied to cis-regulatory modules involved in development of the fruitfly embryo, to elicit known and novel motifs. We finally use the algorithm on genes predictive of social behavior in the honey bee, and find interesting motifs.

Availability: The program is available upon request from the author.

Contact:  sinhas@cs.uiuc.edu
Analysis of sample set enrichment scores: assaying the enrichment of sets of genes for individual samples in genome-wide expression profiles
Authors: Edelman Elena , Porrello Alessandro , Guinney Justin , Balakumaran Bala , Bild Andrea , Febbo Phillip G. , Mukherjee Sayan
Published: July 2006

Motivation: Gene expression profiling experiments in cell lines and animal models characterized by specific genetic or molecular perturbations have yielded sets of genes annotated by the perturbation. These gene sets can serve as a reference base for interrogating other expression datasets. For example, a new dataset in which a specific pathway gene set appears to be enriched, in terms of multiple genes in that set evidencing expression changes, can then be annotated by that reference pathway. We introduce in this paper a formal statistical method to measure the enrichment of each sample in an expression dataset. This allows us to assay the natural variation of pathway activity in observed gene expression data sets from clinical cancer and other studies.

Results: Validation of the method and illustrations of biological insights gleaned are demonstrated on cell line data, mouse models, and cancer-related datasets. Using oncogenic pathway signatures, we show that gene sets built from a model system are indeed enriched in the model system. We employ ASSESS for the use of molecular classification by pathways. This provides an accurate classifier that can be interpreted at the level of pathways instead of individual genes. Finally, ASSESS can be used for cross-platform expression models where data on the same type of cancer are integrated over different platforms into a space of enrichment scores.

Availability: Versions are available in Octave and Java (with a graphical user interface). Software can be downloaded at

Contact:  sayan@stat.duke.edu
A sequence-based filtering method for ncRNA identification and its application to searching for riboswitch elements
Authors: Zhang Shaojie , Borovok Ilya , Aharonowitz Yair , Sharan Roded , Bafna Vineet
Published: July 2006

Motivation: Recent studies have uncovered an “RNA world”, in which non coding RNA (ncRNA) sequences play a central role in the regulation of gene expression. Computational studies on ncRNA have been directed toward developing detection methods for ncRNAs. State-of-the-art methods for the problem, like covariance models, suffer from high computational cost, underscoring the need for efficient filtering approaches that can identify promising sequence segments and speedup the detection process.

Results: In this paper we make several contributions toward this goal. First, we formalize the concept of a filter and provide figures of merit that allow comparison between filters. Second, we design efficient sequence based filters that dominate the current state-of-the-art HMM filters. Third, we provide a new formulation of the covariance model that allows speeding up RNA alignment. We demonstrate the power of our approach on both synthetic data and real bacterial genomes. We then apply our algorithm to the detection of novel riboswitch elements from the whole bacterial and archaeal genomes. Our results point to a number of novel riboswitch candidates, and include genomes that were not previously known to contain riboswitches.

Availability: The program is available upon request from the authors.

Contact:  shzhang@cs.ucsd.edu
A computational approach toward label-free protein quantification using predicted peptide detectability
Authors: Tang Haixu , Arnold Randy J. , Alves Pedro , Xun Zhiyin , Clemmer David E. , Novotny Milos V. , Reilly James P. , Radivojac Predrag
Published: July 2006

Summary: We propose here a new concept of peptide detectability which could be an important factor in explaining the relationship between a protein's quantity and the peptides identified from it in a high-throughput proteomics experiment. We define peptide detectability as the probability of observing a peptide in a standard sample analyzed by a standard proteomics routine and argue that it is an intrinsic property of the peptide sequence and neighboring regions in the parent protein. To test this hypothesis we first used publicly available data and data from our own synthetic samples in which quantities of model proteins were controlled. We then applied machine learning approaches to demonstrate that peptide detectability can be predicted from its sequence and the neighboring regions in the parent protein with satisfactory accuracy. The utility of this approach for protein quantification is demonstrated by peptides with higher detectability generally being identified at lower concentrations over those with lower detectability in the synthetic protein mixtures. These results establish a direct link between protein concentration and peptide detectability. We show that for each protein there exists a level of peptide detectability above which peptides are detected and below which peptides are not detected in an experiment. We call this level the minimum acceptable detectability for identified peptides (MDIP) which can be calibrated to predict protein concentration. Triplicate analysis of a biological sample showed that these MDIP values are consistent among the three data sets.

Contact:  predrag@indiana.edu
Integrating copy number polymorphisms into array CGH analysis using a robust HMM
Authors: Shah Sohrab P. , Xuan Xiang , DeLeeuw Ron J. , Khojasteh Mehrnoush , Lam Wan L. , Ng Raymond , Murphy Kevin P.
Published: July 2006

Motivation: Array comparative genomic hybridization (aCGH) is a pervasive technique used to identify chromosomal aberrations in human diseases, including cancer. Aberrations are defined as regions of increased or decreased DNA copy number, relative to a normal sample. Accurately identifying the locations of these aberrations has many important medical applications. Unfortunately, the observed copy number changes are often corrupted by various sources of noise, making the boundaries hard to detect. One popular current technique uses hidden Markov models (HMMs) to divide the signal into regions of constant copy number called segments; a subsequent classification phase labels each segment as a gain, a loss or neutral. Unfortunately, standard HMMs are sensitive to outliers, causing over-segmentation, where segments erroneously span very short regions.

Results: We propose a simple modification that makes the HMM robust to such outliers. More importantly, this modification allows us to exploit prior knowledge about the likely location of “outliers”, which are often due to copy number polymorphisms (CNPs). By “explaining away” these outliers with prior knowledge about the locations of CNPs, we can focus attention on the more clinically relevant aberrated regions. We show significant improvements over the current state of the art technique (DNAcopy with MergeLevels) on previously published data from mantle cell lymphoma cell lines, and on published benchmark synthetic data augmented with outliers.

Availability: Source code written in Matlab is available from .

Contact: sshah@cs.ubc.ca
Mutation parameters from DNA sequence data using graph theoretic measures on lineage trees
Authors: Magori-Cohen Reuma , Louzoun Yoram , Kleinstein Steven H.
Published: July 2006

Motivation: B cells responding to antigenic stimulation can fine-tune their binding properties through a process of affinity maturation composed of somatic hypermutation, affinity-selection and clonal expansion. The mutation rate of the B cell receptor DNA sequence, and the effect of these mutations on affinity and specificity, are of critical importance for understanding immune and autoimmune processes. Unbiased estimates of these properties are currently lacking due to the short time-scales involved and the small numbers of sequences available.

Results: We have developed a bioinformatic method based on a maximum likelihood analysis of phylogenetic lineage trees to estimate the parameters of a B cell clonal expansion model, which includes somatic hypermutation with the possibility of lethal mutations. Lineage trees are created from clonally related B cell receptor DNA sequences. Important links between tree shapes and underlying model parameters are identified using mutual information. Parameters are estimated using a likelihood function based on the joint distribution of several tree shapes, without requiring a priori knowledge of the number of generations in the clone (which is not available for rapidly dividing populations in vivo). A systematic validation on synthetic trees produced by a mutating birth-death process simulation shows that our estimates are precise and robust to several underlying assumptions. These methods are applied to experimental data from autoimmune mice to demonstrate the existence of hypermutating B cells in an unexpected location in the spleen.

Contact:  stevenk@cs.princeton.edu
SNP Function Portal: a web database for exploring the function implication of SNP alleles
Authors: Wang Pinglang , Dai Manhong , Xuan Weijian , McEachin Richard C. , Jackson Anne U. , Scott Laura J. , Athey Brian , Watson Stanley J. , Meng Fan
Published: July 2006

Motivation: Finding the potential functional significance of SNPs is a major bottleneck in understanding genome-wide SNP scanning results, as the related functional data are distributed across many different databases. The SNP Function Portal is designed to be a clearing house for all public domain SNP functional annotation data, as well as in-house functional annotations derived from different data sources. It currently contains SNP functional annotations in six major categories including genomic elements, transcription regulation, protein function, pathway, disease and population genetics. Besides extensive SNP functional annotations, the SNP Function Portal includes a powerful search engine that accepts different types of genetic markers as input and identifies all genetically related SNPs based on the HapMap Phase II data as well as the relationship of different markers to known genes. As a result, our system allows users to identify the potential biological impact of genetic markers and complex relationships among genetic markers and genes, and it greatly facilitates knowledge discovery in genome-wide SNP scanning experiments.

Availability:  

Contact:  mengf@umich.edu
MotifCut: regulatory motifs finding with maximum density subgraphs
Authors: Fratkin Eugene , Naughton Brian T. , Brutlag Douglas L. , Batzoglou Serafim
Published: July 2006

Motivation: DNA motif finding is one of the core problems in computational biology, for which several probabilistic and discrete approaches have been developed. Most existing methods formulate motif finding as an intractable optimization problem and rely either on expectation maximization (EM) or on local heuristic searches. Another challenge is the choice of motif model: simpler models such as the position-specific scoring matrix (PSSM) impose biologically unrealistic assumptions such as independence of the motif positions, while more involved models are harder to parametrize and learn.

Results: We present MotifCut, a graph-theoretic approach to motif finding leading to a convex optimization problem with a polynomial time solution. We build a graph where the vertices represent all k-mers in the input sequences, and edges represent pairwise k-mer similarity. In this graph, we search for a motif as the maximum density subgraph, which is a set of k-mers that exhibit a large number of pairwise similarities. Our formulation does not make strong assumptions regarding the structure of the motif and in practice both motifs that fit well the PSSM model, and those that exhibit strong dependencies between position pairs are found as dense subgraphs. We benchmark MotifCut on both synthetic and real yeast motifs, and find that it compares favorably to existing popular methods. The ability of MotifCut to detect motifs appears to scale well with increasing input size. Moreover, the motifs we discover are different from those discovered by the other methods.

Availability: MotifCut server and other materials can be found at motifcut.stanford.edu

Contact:  fratkin@cs.stanford.edu
CONTRAfold: RNA secondary structure prediction without physics-based models
Authors: Do Chuong B. , Woods Daniel A. , Batzoglou Serafim
Published: July 2006

Motivation: For several decades, free energy minimization methods have been the dominant strategy for single sequence RNA secondary structure prediction. More recently, stochastic context-free grammars (SCFGs) have emerged as an alternative probabilistic methodology for modeling RNA structure. Unlike physics-based methods, which rely on thousands of experimentally-measured thermodynamic parameters, SCFGs use fully-automated statistical learning algorithms to derive model parameters. Despite this advantage, however, probabilistic methods have not replaced free energy minimization methods as the tool of choice for secondary structure prediction, as the accuracies of the best current SCFGs have yet to match those of the best physics-based models.

Results: In this paper, we present CONTRAfold, a novel secondary structure prediction method based on conditional log-linear models (CLLMs), a flexible class of probabilistic models which generalize upon SCFGs by using discriminative training and feature-rich scoring. In a series of cross-validation experiments, we show that grammar-based secondary structure prediction methods formulated as CLLMs consistently outperform their SCFG analogs. Furthermore, CONTRAfold, a CLLM incorporating most of the features found in typical thermodynamic models, achieves the highest single sequence prediction accuracies to date, outperforming currently available probabilistic and physics-based techniques. Our result thus closes the gap between probabilistic and thermodynamic models, demonstrating that statistical learning procedures provide an effective alternative to empirical measurement of thermodynamic parameters for RNA secondary structure prediction.

Availability: Source code for CONTRAfold is available at .

Contact:  chuongdo@cs.stanford.edu
ARTS: accurate recognition of transcription starts in human
Authors: Sonnenburg Sören , Zien Alexander , Rätsch Gunnar
Published: July 2006

We develop new methods for finding transcription start sites (TSS) of RNA Polymerase II binding genes in genomic DNA sequences. Employing Support Vector Machines with advanced sequence kernels, we achieve drastically higher prediction accuracies than state-of-the-art methods.

Motivation: One of the most important features of genomic DNA are the protein-coding genes. While it is of great value to identify those genes and the encoded proteins, it is also crucial to understand how their transcription is regulated. To this end one has to identify the corresponding promoters and the contained transcription factor binding sites. TSS finders can be used to locate potential promoters. They may also be used in combination with other signal and content detectors to resolve entire gene structures.

Results: We have developed a novel kernel based method – called ARTS – that accurately recognizes transcription start sites in human. The application of otherwise too computationally expensive Support Vector Machines was made possible due to the use of efficient training and evaluation techniques using suffix tries. In a carefully designed experimental study, we compare our TSS finder to state-of-the-art methods from the literature: McPromoter, Eponine and FirstEF. For given false positive rates within a reasonable range, we consistently achieve considerably higher true positive rates. For instance, ARTS finds about 35% true positives at a false positive rate of 1/1000, where the other methods find about a half (18%).

Availability: Datasets, model selection results, whole genome predictions, and additional experimental results are available at

Contact:  Gunnar.Raetsch@tuebingen.mpg.de
Learning MHC I—peptide binding
Authors: Jojic Nebojsa , Reyes-Gomez Manuel , Heckerman David , Kadie Carl , Schueler-Furman Ora
Published: July 2006

Motivation and results: Motivated by the ability of a simple threading approach to predict MHC I—peptide binding, we developed a new and improved structure-based model for which parameters can be estimated from additional sources of data about MHC-peptide binding. In addition to the known 3D structures of a small number of MHC-peptide complexes that were used in the original threading approach, we included three other sources of information on peptide-MHC binding: (1) MHC class I sequences; (2) known binding energies for a large number of MHC-peptide complexes; and (3) an even larger binary dataset that contains information about strong binders (epitopes) and non-binders (peptides that have a low affinity for a particular MHC molecule). Our model significantly outperforms the standard threading approach in binding energy prediction. In our approach, which we call adaptive double threading, the parameters of the threading model are learnable, and both MHC and peptide sequences can be threaded onto structures of other alleles. These two properties make our model appropriate for predicting binding for alleles for which very little data (if any) is available beyond just their sequence, including prediction for alleles for which 3D structures are not available. The ability of our model to generalize beyond the MHC types for which training data is available also separates our approach from epitope prediction methods which treat MHC alleles as symbolic types, rather than biological sequences. We used the trained binding energy predictor to study viral infections in 246 HIV patients from the West Australian cohort, and over 1000 sequences in HIV clade B from Los Alamos National Laboratory database, capturing the course of HIV evolution over the last 20 years. Finally, we illustrate short-, medium-, and long-term adaptation of HIV to the human immune system.

Availability:  

Contact:  jojic@microsoft.com
Hairpins in a Haystack: recognizing microRNA precursors in comparative genomics data
Authors: Hertel Jana , Stadler Peter F.
Published: July 2006

Summary: Recently, genome-wide surveys for non-coding RNAs have provided evidence for tens of thousands of previously undescribed evolutionary conserved RNAs with distinctive secondary structures. The annotation of these putative ncRNAs, however, remains a difficult problem. Here we describe an SVM-based approach that, in conjunction with a non-stringent filter for consensus secondary structures, is capable of efficiently recognizing microRNA precursors in multiple sequence alignments. The software was applied to recent genome-wide RNAz surveys of mammals, urochordates, and nematodes.

Availability: The program RNAmicro is available as source code and can be downloaded from

Contact:Jana Hertel, Tel: ++49 341 97 16704, Fax: ++49 341 97 16709, {jana,studla}@bioinf.uni-leipzig.de
Distance based algorithms for small biomolecule classification and structural similarity search
Authors: Karakoc Emre , Cherkasov Artem , Sahinalp S. Cenk
Published: July 2006

Motivation: Structural similarity search among small molecules is a standard tool used in molecular classification and in-silico drug discovery. The effectiveness of this general approach depends on how well the following problems are addressed. The notion of similarity should be chosen for providing the highest level of discrimination of compounds wrt the bioactivity of interest. The data structure for performing search should be very efficient as the molecular databases of interest include several millions of compounds.

Results: In this paper we focus on the k-nearest-neighbor search method, which, until recently was not considered for small molecule classification. The few recent applications of k-nn to compound classification focus on selecting the most relevant set of chemical descriptors which are then compared under standard Minkowski distance Lp. Here we show how to computationally design the optimal weighted Minkowski distance wLp for maximizing the discrimination between active and inactive compounds wrt bioactivities of interest. We then show how to construct pruning based k-nn search data structures for any wLp distance that minimizes similarity search time.

The accuracy achieved by our classifier is better than the alternative LDA and MLR approaches and is comparable to the ANN methods. In terms of running time, our classifier is considerably faster than the ANN approach especially when large data sets are used. Furthermore, our classifier quantifies the level of bioactivity rather than returning a binary decision and thus is more informative than the ANN approach.

Contact:  cenk@cs.sfu.ca
Dense subgraph computation via stochastic search: application to detect transcriptional modules
Authors: Everett Logan , Wang Li-San , Hannenhalli Sridhar
Published: July 2006

Motivation: In a tri-partite biological network of transcription factors, their putative target genes, and the tissues in which the target genes are differentially expressed, a tightly inter-connected (dense) subgraph may reveal knowledge about tissue specific transcription regulation mediated by a specific set of transcription factors—a tissue-specific transcriptional module. This is just one context in which an efficient computation of dense subgraphs in a multi-partite graph is needed.

Result: Here we report a generic stochastic search based method to compute dense subgraphs in a graph with an arbitrary number of partitions and an arbitrary connectivity among the partitions. We then use the tool to explore tissue-specific transcriptional regulation in the human genome. We validate our findings in Skeletal muscle based on literature. We could accurately deduce biological processes for transcription factors via the tri-partite clusters of transcription factors, genes, and the functional annotation of genes. Additionally, we propose a few previously unknown TF-pathway associations and tissue-specific roles for certain pathways. Finally, our combined analysis of Cardiac, Skeletal, and Smooth muscle data recapitulates the evolutionary relationship among the three tissues.

Contact:  sridharh@pcbi.upenn.edu