bluuebunny/crossref_metadata_2025 huggingface dataset:
Coherent imaging of nanoscale plasmon patterns with a carbon nanotube optical probe
Authors: Hillenbrand R. , Keilmann F. , Hanarp P. , Sutherland D. S. , Aizpurua J.
Published: July 2003

We introduce a carbon nanotube as optical near-field probe and apply it to visualize the plasmon fields of metal nanostructures in both amplitude and phase at 30 nm resolution. With 91 nm Au disks designed for fundamental plasmon resonance, we observe the antiphase optical fields near two pole regions that are evidence of dipolar oscillation, in good agreement with theoretical field patterns. This opens the door to phase-sensitively map optical propagation and storage in photonic crystals and nanooptic resonators or circuits, in particular to verify coherent control of plasmon polaritons.
Red electrophosphorescence devices based on rhenium complexes
Authors: Li Feng , Zhang Ming , Feng Jing , Cheng Gang , Wu Zhijun , Ma Yuguang , Liu Shiyong , Sheng Jiacong , Lee S. T.
Published: July 2003

Red electrophosphorescence from light-emitting devices based on two rhenium(I) diimine complexes, (4,4′-dimethyl formate-2,2′-bipyridine)Re(CO)3Cl (dmfbpy-Re) and (4,4′-dibutyl formate-2,2′-bipyridine)Re(CO)3Cl (dbufbpy-Re), is reported. N, N′-di-1-naphthyl-N, N′-diphenylbenzidine is used as the hole-transporting layer. 2,9-dimethyl-4,7-diphenyl-1,10-phenanthroline, bathocuproine is used to confine excitons within the luminescence zone. dmfbpy-Re and dbufbpy-Re are doped into the host materials (4,4′-N-N′-dicarbazole)biphenyl with mass ratios of 2%–20% as the light-emitting layer. Red emission from both complexes is achieved and the main peaks of both photoluminescence and electroluminescence are at about 610 nm. The turn-on voltage, maximum efficiency, and brightness for red emission achieved from the devices based on dmfbpy-Re and dbufbpy-Re are ∼5 V, 1.3 cd/A, and 582 cd/m2 and ∼4 V, 1.1 cd/A, and 739 cd/m2, respectively.
Strong photoluminescence and cathodoluminescence due to f–f transitions in Eu3+ doped Al2O3 powders prepared by direct combustion synthesis and thin films deposited by laser ablation
Authors: Rakov Nikifor , Ramos Francisco E. , Hirata Gustavo , Xiao Mufei
Published: July 2003

In this letter, we report on fabrication and luminescent properties of phosphor powders and thin films of Eu3+ doped alumina Al2O3. The powders were fabricated by combustion synthesis process at a low temperature, 280 °C and showed strong photoluminescent and cathodoluminescent emissions. Powders of Eu3+ doped Al2O3 of concentration 1.0 mol % were deposited on quartz-glass substrates to form thin films by means of laser ablation. Under ultraviolet excitation and electron beam excitation, these samples containing microcrystalline structures showed strong luminescence due to f–f transitions, and the dominant transition was the hypersensitive D40→F72 red emission of Eu3+.
Relaxation times in exchange-biased nanostructures
Authors: Mejı́a-López José , Altbir D. , Schuller Iván K.
Published: July 2003

We calculated the energy barrier, ΔE, for exchange-biased (EB) systems, using the ferromagnetic domain wall model. The temperature dependence of the EB is in good agreement with experimental results. For Fe–FeF2, Fe–MnF2, and Ni–NiO, ΔE is proportional to a power of the interfacial coupling constant and inversely to the ferromagnetic film thickness. The temperature and volume dependence of the relaxation time show that exchange coupling increases the superparamagnetic blocking temperature of nanostructured ferromagnets.
Single-electron transistor based on modulation-doped SiGe heterostructures
Authors: Notargiacomo A. , Di Gaspare L. , Scappucci G. , Mariottini G. , Evangelisti F. , Giovine E. , Leoni R.
Published: July 2003

We report the characterization of a single-electron transistor based on bended wires fabricated on modulation-doped SiGe two-dimensional electron gas. Electrical measurements show a diamond-shaped stability plot and a nonperiodic sequence of conductance peaks. The device behavior suggests the presence of disorder-induced multiple islands along the wire. Conductance oscillations remain well pronounced above liquid helium temperature.
Oxygen profile engineering in silicon by germanium addition and high-temperature annealing
Authors: An Zhenghua , Chu Paul K. , Zhang Miao , Men Chuanling , Lin Chenglu
Published: July 2003

The formation of multilayer structures in oxygen-implanted silicon by the introduction of germanium is reported. Our results show that the oxygen distribution can be split under carefully controlled annealing conditions. The typical annealing process consists of first raising the furnace temperature from 600 to 1200 °C within 30 min and then holding the temperature at 1200 °C for 2 h. The faster crystallization rate of amorphous silicon germanium (SiGe) and germanium rejection from the oxide contribute to the final multilayer structure. Our findings suggest that oxygen profile engineering is possible and single-energy ion implantation can be utilized to fabricate multilayer structures containing multiple buried oxide layers. In addition, our results suggest that, in SiGe-on-insulator fabrication, the annealing step at a moderate temperature or a slow temperature ramp-up rate during the high-temperature annealing step is much more critical than in conventional silicon-on-insulator fabrication.
Effect of oxygen on the electronic band structure in ZnOxSe1−x alloys
Authors: Shan W. , Walukiewicz W. , Ager J. W. , Yu K. M. , Wu J. , Haller E. E. , Nabetani Y. , Mukawa T. , Ito Y. , Matsumoto T.
Published: July 2003

The effect of alloying small amounts of ZnO with ZnSe on the electronic band structure has been studied. Optical transitions in molecular-beam-epitaxy-grown ZnOxSe1−x epitaxial films (0⩽x⩽1.35%) were investigated using photoreflectance and photoluminescence spectroscopies. The fundamental band-gap energy of the alloys was found to decrease at a rate of about 0.1 eV per atomic percent of oxygen. The pressure dependence of the band gap was also found to be strongly affected by O incorporation. Both the effects can be quantitatively explained by an anticrossing interaction between the extended states of the conduction band of ZnSe and the highly localized oxygen states located at approximately 0.22 eV above the conduction-band edge.
Tunable terahertz wave generation in the 3- to 7-THz region from GaP
Authors: Tanabe T. , Suto K. , Nishizawa J. , Saito K. , Kimura T.
Published: July 2003

Following the generation of tunable terahertz waves from GaP in the 0.5- to 3-THz region, we extended the frequency region up to 7 THz, using an optical parametric oscillator and a YAG laser (1.064 μm). The tuning angle θin increased superlinearly in the 3- to 7-THz region, so that the total reflection took place at 5 THz, which was avoided by rotating the crystal relative to the incident optic axis. As a result, terahertz output peak powers of 100 mW at up to 5.6 THz and 3 mW at 7 THz were obtained, at pump and signal energies of 3 mJ, respectively.
Effect of crystal nature on upconversion luminescence in Er3+:ZrO2 nanocrystals
Authors: Patra Amitava , Friend Christopher S. , Kapoor Rakesh , Prasad Paras N.
Published: July 2003

The effects of crystal size and crystal phase on the upconverted emission of Er3+ in ZrO2 oxide nanocrystals are reported. Green (550 nm) and red (670 nm) upconversion emission were observed at room temperature from the S43/2 and F49/2 levels of Er3+:ZrO2 nanocrystals. It is found that at 850 mW of cw excitation power, the total luminescence was 11960 Cd/m2 for 1000 °C heated sample. We observed that the overall upconversion luminescence intensity depends on crystal structure and particle size. We have also confirmed that upconversion process in all these samples results from a two-photon excited-state absorption process.
Unification of zero-sum problems, subset sums and covers of ℤ
Authors: Sun Zhi-Wei
Published: July 2003

In combinatorial number theory, zero-sum problems, subset sums and covers of the integers are three different topics initiated by P. Erdös and investigated by many researchers; they play important roles in both number theory and combinatorics. In this paper we announce some deep connections among these seemingly unrelated fascinating areas, and aim at establishing a unified theory! Our main theorem unifies many results in these three realms and also has applications in many aspects such as finite fields and graph theory. To illustrate this, here we state our extension of the Erdös-Ginzburg-Ziv theorem: If

A
=
{

a

s

(

m
o
d

 

n

s

)

}

s
=
1

k

A=\{a_{s}(\mathrm {mod}\ n_{s})\}_{s=1}^{k}

covers some integers exactly

2
p
−
1

2p-1

times and others exactly

2
p

2p

times, where

p
p

is a prime, then for any

c

1

,
⋯
,

c

k

∈

Z

/

p

Z

c_{1},\cdots ,c_{k}\in \mathbb {Z}/p\mathbb {Z}

there exists an

I
⊆
{
1
,
⋯
,
k
}

I\subseteq \{1,\cdots ,k\}

such that

∑

s
∈
I

1

/

n

s

=
p

\sum _{s\in I}1/n_{s}=p

and

∑

s
∈
I

c

s

=
0

\sum _{s\in I}c_{s}=0

.
Bayesian gene/species tree reconciliation
and orthology analysis using MCMC
Authors: Arvestad Lars , Berglund Ann-Charlotte , Lagergren Jens , Sennblad Bengt
Published: July 2003

Motivation: Comparative genomics in general and orthology analysis in particular are becoming increasingly important parts of gene function prediction. Previously, orthology analysis and reconciliation has been performed only with respect to the parsimony model. This discards many plausible solutions and sometimes precludes finding the correct one. In many other areas in bioinformatics probabilistic models have proven to be both more realistic and powerful than parsimony models. For instance, they allow for assessing solution reliability and consideration of alternative solutions in a uniform way. There is also an added benefit in making model assumptions explicit and therefore making model comparisons possible. For orthology analysis, uncertainty has recently been addressed using parsimonious reconciliation combined with bootstrap techniques. However, until now no probabilistic methods have been available.

Results: We introduce a probabilistic gene evolution model based on a birth-death process in which a gene tree evolves ‘inside’ a species tree. Based on this model, we develop a tool with the capacity to perform practical orthology analysis, based on Fitch’s original definition, and more generally for reconciling pairs of gene and species trees. Our gene evolution model is biologically sound (Nei et al., 1997) and intuitively attractive. We develop a Bayesian analysis based on MCMC which facilitates approximation of an a posteriori distribution for reconciliations. That is, we can find the most probable reconciliations and estimate the probability of any reconciliation, given the observed gene tree. This also gives a way to estimate the probability that a pair of genes are orthologs. The main algorithmic contribution presented here consists of an algorithm for computing the likelihood of a given reconciliation. To the best of our knowledge, this is the first successful introduction of this type of probabilistic methods, which flourish in phylogeny analysis, into reconciliation and orthology analysis. The MCMC algorithm has been implemented and, although not yet being in its final form, tests show that it performs very well on synthetic as well as biological data. Using standard correspondences, our results carry over to allele trees as well as biogeography.

Contact: {lottab,jensl}@nada.kth.se, {bengt.sennblad,lars.arvestad}@sbc.su.se

*To whom correspondence should be addressed.
Predicting bacterial transcription units using sequence and expression data
Authors: Bockhorst Joseph , Qiu Yu , Glasner Jeremy , Liu Mingzhu , Blattner Frederick , Craven Mark
Published: July 2003

Motivation: A key aspect of elucidating gene regulation in bacterial genomes is identifying the basic units of transcription. We present a method, based on probabilistic language models, that we apply to predict operons, promoters and terminators in the genome of Escherichia coli K-12. Our approach has two key properties: (i) it provides a coherent set of predictions for related regulatory elements of various types and (ii) it takes advantage of both DNA sequence and gene expression data, including expression measurements from inter-genic probes.

Results: Our experimental results show that we are able to predict operons and localize promoters and terminators with high accuracy. Moreover, our models that use both sequence and expression data are more accurate than those that use only one of these two data sources.

Availability: Our E.coli transcription-unit predictions are available from http://www.biostat.wisc.edu/gene-regulation/

Contact: joebock@biostat.wisc.edu; craven@biostat.wisc.edu

*To whom correspondence should be addressed.
Glocal alignment: finding rearrangements during alignment
Authors: Brudno Michael , Malde Sanket , Poliakov Alexander , Do Chuong B. , Couronne Olivier , Dubchak Inna , Batzoglou Serafim
Published: July 2003

Motivation: To compare entire genomes from different species, biologists increasingly need alignment methods that are efficient enough to handle long sequences, and accurate enough to correctly align the conserved biological features between distant species. The two main classes of pairwise alignments are global alignment, where one string is transformed into the other, and local alignment, where all locations of similarity between the two strings are returned. Global alignments are less prone to demonstrating false homology as each letter of one sequence is constrained to being aligned to only one letter of the other. Local alignments, on the other hand, can cope with rearrangements between non-syntenic, orthologous sequences by identifying similar regions in sequences; this, however, comes at the expense of a higher false positive rate due to the inability of local aligners to take into account overall conservation maps.

Results: In this paper we introduce the notion of glocal alignment, a combination of global and local methods, where one creates a map that transforms one sequence into the other while allowing for rearrangement events. We present Shuffle-LAGAN, a glocal alignment algorithm that is based on the CHAOS local alignment algorithm and the LAGAN global aligner, and is able to align long genomic sequences. To test Shuffle-LAGAN we split the mouse genome into BAC-sized pieces, and aligned these pieces to the human genome. We demonstrate that Shuffle-LAGAN compares favorably in terms of sensitivity and specificity with standard local and global aligners. From the alignments we conclude that about 9% of human/mouse homology may be attributed to small rearrangements, 63% of which are duplications.

Availability: Our systems, supplemental information, and the alignment of the human and mouse genomes using Shuffle-LAGAN are available at http://lagan.stanford.edu/glocal

Contact: serafim@cs.stanford.edu

*To whom correspondence should be addressed.

†These authors contributed equally to the work.
Linking genotype to phenotype: the International Rice Information System (IRIS)
Authors: Bruskiewich Richard M. , Cosico Alexander B. , Eusebio William , Portugal Arllet M. , Ramos Luralyn M. , Reyes Ma. Teresa , Sallan May Ann B. , Ulat Victor Jun M. , Wang Xusheng , McNally Kenneth L. , Sackville Hamilton Ruaraidh , McLaren Christopher Graham
Published: July 2003

The International Rice Information System (IRIS, http://www.iris.irri.org) is the rice implementation of the International Crop Information System (ICIS, http://www.icis.cgiar.org), a database system for the management and integration of global information on genetic resources and germplasm improvement for any crop. Building upon the germplasm genealogy and field data components of ICIS, IRIS is being extended to handle diverse rice genomics data including: genetic mapping, genome annotation, genotype, mutant, transcripteome, proteome and metabolomic data. Users can access information in the database through stand-alone programs and WWW interfaces offering specialist views to researchers with different interests.

Availability: http://bioinformatics.org/project/?group_id=141

Contact: r.bruskiewich@cgiar.org

Keywords: database, crop, rice, germplasm, genotype, phenotype, genomics

*To whom correspondence should be addressed.
Stochastic modeling of RNA pseudoknotted structures: a grammatical
approach
Authors: Cai Liming , Malmberg Russell L. , Wu Yunzhou
Published: July 2003

Motivation: Modeling RNA pseudoknotted structures remains challenging. Methods have previously been developed to model RNA stem-loops successfully using stochastic context-free grammars (SCFG) adapted from computational linguistics; however, the additional complexity of pseudoknots has made modeling them more difficult. Formally a context-sensitive grammar is required, which would impose a large increase in complexity.

Results: We introduce a new grammar modeling approach for RNA pseudoknotted structures based on parallel communicating grammar systems (PCGS). Our new approach can specify pseudoknotted structures, while avoiding context-sensitive rules, using a single CFG synchronized with a number of regular grammars. Technically, the stochastic version of the grammar model can be as simple as an SCFG. As with SCFG, the new approach permits automatic generation of a single-RNA structure prediction algorithm for each specified pseudoknotted structure model. This approach also makes it possible to develop full probabilistic models of pseudoknotted structures to allow the prediction of consensus structures by comparative analysis and structural homology recognition in database searches.

Availability: Prototypes for the automated pseudoknot prediction algorithm are available upon request.

Contact: cai@cs.uga.edu; russell@plantbio.uga.edu

*To whom correspondence should be addressed.
Fast identification and statistical evaluation of
segmental homologies in comparative maps
Authors: Calabrese Peter P. , Chakravarty Sugata , Vision Todd J.
Published: July 2003

Motivation: Chromosomal segments that share common ancestry, either through genomic duplication or species divergence, are said to be segmental homologs of one another. Their identification allows researchers to leverage knowledge of model organisms for use in other systems and is of value for studies of genome evolution. However, identification and statistical evaluation of segmental homologies can be a challenge when the segments are highly diverged.

Results: We describe a flexible dynamic programming algorithm for the identification of segments having multiple homologous features. We model the probability of observing putative segmental homologies by chance and incorporate our findings into the parameterization of the algorithm and the statistical evaluation of its output. Combined, these findings allow segmental homologies to be identified in comparisons within and between genomic maps in a rigorous, rapid, and automated fashion.

Availability: http://www.bio.unc.edu/faculty/vision/lab/

Contact: tjv@bio.unc.edu

Keywords: homology, comparative maps, synteny, genome evolution

*To whom correspondence should be addressed.
PSI: indexing protein structures for fast similarity search
Authors: Camoglu Orhan , Kahveci Tamer , Singh Ambuj K.
Published: July 2003

Motivation: We consider the problem of finding similarities in protein structure databases. Current techniques sequentially compare the given query protein to all of the proteins in the database to find similarities. Therefore, the cost of similarity queries increases linearly as the volume of the protein databases increase. As the sizes of experimentally determined and theoretically estimated protein structure databases grow, there is a need for scalable searching techniques.

Results: Our techniques extract feature vectors on triplets of SSEs (Secondary Structure Elements). Later, these feature vectors are indexed using a multidimensional index structure. For a given query protein, this index structure is used to quickly prune away unpromising proteins in the database. The remaining proteins are then aligned using a popular alignment tool such as VAST. We also develop a novel statistical model to estimate the goodness of a match using the SSEs. Experimental results show that our techniques improve the pruning time of VAST 3 to 3.5 times while maintaining similar sensitivity.

Contact: orhan@cs.ucsb.edu; tamer@cs.ucsb.edu; ambuj@cs.ucsb.edu.

Keywords: Protein structures, feature vectors, indexing

*To whom correspondence should be addressed.
MASS: multiple structural alignment by secondary structures
Authors: Dror O. , Benyamini H. , Nussinov R. , Wolfson H.
Published: July 2003

We present a novel method for multiple alignment of protein structures and detection of structural motifs. To date, only a few methods are available for addressing this task. Most of them are based on a series of pairwise comparisons. In contrast, MASS (Multiple Alignment by Secondary Structures) considers all the given structures at the same time. Exploiting the secondary structure representation aids in filtering out noisy results and in making the method highly efficient and robust. MASS disregards the sequence order of the secondary structure elements. Thus, it can find non-sequential and even non-topological structural motifs. An important novel feature of MASS is subset alignment detection: It does not require that all the input molecules be aligned. Rather, MASS is capable of detecting structural motifs shared only by a subset of the molecules. Given its high efficiency and capability of detecting subset alignments, MASS is suitable for a broad range of challenging applications: It can handle large-scale protein ensembles (on the order of tens) that may be heterogeneous, noisy, topologically unrelated and contain structures of low resolution.

Keywords: Structural Bioinformatics, Subset alignment, Non-sequential alignment, Non-topological motif, Supersecondary structural motif

Availability: MASS program and more information about it are available on http://bioinfo3d.cs.tau.ac.il/MASS

Contact: oranit@post.tau.ac.il

*To whom correspondence should be addressed.
Annotation of bacterial genomes using improved phylogenomic profiles
Authors: Enault F. , Suhre K. , Abergel C. , Poirot O. , Claverie J.-M.
Published: July 2003

Motivation: Phylogenomic profiling is a large-scale comparative genomic method used to infer protein function from evolutionary information first described in a binary form by Pellegrini et al. (1999). Here, we propose improvements of this approach including the use of normalized Blastp bit scores, a normalization of the matrix of profiles to take into account the evolutionary distances between bacteria, the definition of a phylogenomic neighborhood based on continuous pairwise distances between genes and an original annotation procedure including the computation of a p-value for each functional assignment.

Results: The method presented here increases the number of Ecocyc enzymes identified as being evolutionarily related by about 25% with respect to the original binary form (absent/present) method. The fraction of ‘false’ positives is shown to be smaller than 20%. Based on their phylogenomic relationships, genes of unknown function can then be automatically related to annotated genes. Each gene annotation predicted is associated with a p-value, i.e. its probability to be obtained by chance. The validity of this method was extensively tested on a large set of genes of known function using the MultiFun database. We find that 50% of 3122 function attributions that can be made at a p-value level of 10−11 correspond to the actual gene annotation. The method can be readily applied to any newly sequenced microbial genome. In contrast to earlier work on the same topic, our approach avoids the use of arbitrary cut-off values, and provides a reliability estimate of the functional predictions in form of p-values.

Contact: enault@igs.cnrs-mrs.fr

Keywords: phylogenomics, functional prediction, automated annotation, bacteria, evolution.

*To whom correspondence should be addressed.
Chain functions and scoring functions in genetic networks
Authors: Gat-Viks I. , Shamir R.
Published: July 2003

One of the grand challenges of system biology is to reconstruct the network of regulatory control among genes and proteins. High throughput data, particularly from expression experiments, may gradually make this possible in the future. Here we address two key ingredients in any such ‘reverse engineering’ effort: The choice of a biologically relevant, yet restricted, set of potential regulation functions, and the appropriate score to evaluate candidate regulatory relations.

We propose a set of regulation functions which we call chain functions, and argue for their ubiquity in biological networks. We analyze their complexity and show that their number is exponentially smaller than all boolean functions of the same dimension. We define two new scores: one evaluating the fitness of a candidate set of regulators of a particular gene, and the other evaluating a candidate function. Both scores use established statistical methods. Finally, we test our methods on experimental gene expression data from the yeast galactose pathway. We show the utility of using chain functions and the improved inference using our scores in comparison to several extant scores. We demonstrate that the combined use of the two scores gives an extra advantage. We expect both chain functions and the new scores to be helpful in future attempts to infer regulatory networks.

Contact: {iritg,rshamir}@post.tau.ac.il

*To whom correspondence should be addressed.
Widespread predicted nonsense-mediated mRNA
decay of alternatively-spliced transcripts of human
normal and disease genes
Authors: Green Richard E. , Lewis Benjamin P. , Hillman R. Tyler , Blanchette Marco , Lareau Liana F. , Garnett Aaron T. , Rio Donald C. , Brenner Steven E.
Published: July 2003

We have recently shown that a third of reliably-inferred alternative mRNA isoforms are candidates for nonsense-mediated mRNA decay (NMD), an mRNA surveillance system (Lewis et al., 2003; Proc. Natl Acad. Sci. USA, 100, 189–192). Rather than being translated to yield protein, these transcripts are expected to be degraded and may be subject to regulated unproductive splicing and translation (RUST). Our initial experimental studies are consistent with these predictions and suggest an unappreciated role for NMD in several human diseases.

Contact: brenner@compbio.berkeley.edu

*To whom correspondence should be addressed.
Detecting protein sequence conservation via metric embeddings
Authors: Halperin E. , Buhler J. , Karp R. , Krauthgamer R. , Westover B.
Published: July 2003

Motivation: Comparing two protein databases is a fundamental task in biosequence annotation. Given two databases, one must find all pairs of proteins that align with high score under a biologically meaningful substitution score matrix, such as a BLOSUM matrix (Henikoff and Henikoff, 1992). Distance-based approaches to this problem map each peptide in the database to a point in a metric space, such that peptides aligning with higher scores are mapped to closer points. Many techniques exist to discover close pairs of points in a metric space efficiently, but the challenge in applying this work to proteomic comparison is to find a distance mapping that accurately encodes all the distinctions among residue pairs made by a proteomic score matrix. Buhler (2002) proposed one such mapping but found that it led to a relatively inefficient algorithm for protein-protein comparison.

Results: This work proposes a new distance mapping for peptides under the BLOSUM matrices that permits more efficient similarity search. We first propose a new distance function on peptides derived from a given score matrix. We then show how to map peptides to bit vectors such that the distance between any two peptides is closely approximated by the Hamming distance (i.e. number of mismatches) between their corresponding bit vectors. We combine these two results with the lsh-all-pairs-sim algorithm of Buhler (2002) to produce an improved distance-based algorithm for proteomic comparison. An initial implementation of the improved algorithm exhibits sensitivity within 5% of that of the original lsh-all-pairs-sim, while running up to eight times faster.

Availability: The source of the code can be found at http://www.eecs.berkeley.edu/~eran/projects/embed

Contact: eran@eecs.berkeley.edu

Keywords: protein comparison, database indexing, metric embedding, Hamming space

*To whom correspondence should be addressed.
Sensitive pattern discovery with ‘fuzzy’ alignments of distantly
related proteins
Authors: Heger Andreas , Holm Liisa
Published: July 2003

Motivation: Evolutionary comparison leads to efficient functional characterisation of hypothetical proteins. Here, our goal is to map specific sequence patterns to putative functional classes. The evolutionary signal stands out most clearly in a maximally diverse set of homologues. This diversity, however, leads to a number of technical difficulties. The targeted patterns—as gleaned from structure comparisons—are too sparse for statistically significant signals of sequence similarity and accurate multiple sequence alignment.

Results: We address this problem by a fuzzy alignment model, which probabilistically assigns residues to structurally equivalent positions (attributes) of the proteins. We then apply multivariate analysis to the ‘attributes x proteins’ matrix. The dimensionality of the space is reduced using non-negative matrix factorization. The method is general, fully automatic and works without assumptions about pattern density, minimum support, explicit multiple alignments, phylogenetic trees, etc. We demonstrate the discovery of biologically meaningful patterns in an extremely diverse superfamily related to urease.

Contact: Liisa.Holm@Helsinki.fi

*To whom correspondence should be addressed.
Deriving phylogenetic trees from the similarity analysis of metabolic
pathways
Authors: Heymans Maureen , Singh Ambuj K.
Published: July 2003

Motivation: Comparative analysis of metabolic pathways in different genomes can give insights into the understanding of evolutionary and organizational relationships among species. This type of analysis allows one to measure the evolution of complete processes (with different functional roles) rather than the individual elements of a conventional analysis. We present a new technique for the phylogenetic analysis of metabolic pathways based on the topology of the underlying graphs. A distance measure between graphs is defined using the similarity between nodes of the graphs and the structural relationship between them. This distance measure is applied to the enzyme-enzyme relational graphs derived from metabolic pathways. Using this approach, pathways and group of pathways of different organisms are compared to each other and the resulting distance matrix is used to obtain a phylogenetic tree.

Results: We apply the method to the Citric Acid Cycle and the Glycolysis pathways of different groups of organisms, as well as to the Carbohydrate metabolic networks. Phylogenetic trees obtained from the experiments were close to existing phylogenies and revealed interesting relationships among organisms.

Availability: Software available upon request from the authors.

Supplementary information: The technical report is available at http://www.cs.ucsb.edu/~maureen/TR200233.pdf

Contact: ambuj@cs.ucsb.edu

Keywords: phylogenetic trees, metabolic pathways, graph comparison

*To whom correspondence should be addressed.
Using guide trees to construct multiple-sequence evolutionary HMMs
Authors: Holmes I.
Published: July 2003

Motivation: Score-based progressive alignment algorithms do dynamic programming on successive branches of a guide tree. The analogous probabilistic construct is an Evolutionary HMM. This is a multiple-sequence hidden Markov model (HMM) made by combining transducers (conditionally normalised Pair HMMs) on the branches of a phylogenetic tree.

Methods: We present general algorithms for constructing an Evolutionary HMM from any Pair HMM and for doing dynamic programming to any Multiple-sequence HMM.

Results: Our prototype implementation, Handel, is based on the Thorne-Kishino-Felsenstein evolutionary model and is benchmarked using structural reference alignments.

Availability: Handel can be downloaded under GPL from www.biowiki.org/Handel
Identification of functional clusters
of transcription factor binding motifs in genome
sequences: the MSCAN algorithm
Authors: Johansson Ö. , Alkema W. , Wasserman W. W. , Lagergren J.
Published: July 2003

Motivation:The identification of regulatory control regions within genomes is a major challenge. Studies have demonstrated that regulating regions can be described as locally dense clusters or modules of cis-acting transcription factor binding sites (TFBS). For well-described biological contexts, it is possible to train predictive algorithms to discern novel modules in genome sequences. However, utility of module detection methods has been severely limited by insufficient training data. For only a few tissues can one obtain sufficient numbers of literature-derived regulatory modules.

Results: We present a novel method, MSCAN, that circumvents the training data problem by measuring the statistical significance of any non-overlapping combination of TFBS in a window. Given a set of transcription factor binding profiles, a significance threshold, and a genomic sequence, MSCAN returns putative regulatory regions. We assess performance on two curated collections of regulatory regions; one each for tissue-specific expression in liver and skeletal muscle cells. The efficiency of MSCAN allows for predictive screens of entire genomes.

Availability: http://tfscan.cgb.ki.se/cgi-bin/MSCAN

Contact: wyeth@cmmt.ubc.ca

Keywords: transcription, gene networks, modules, motif, promoter.

*To whom correspondence should be addressed.
Complexity management in visualizing protein interaction networks
Authors: Ju Byong-Hyon , Han Kyungsook
Published: July 2003

Motivation: Protein-protein interaction networks often consist of thousands of nodes or more. This severely limits the utility of many graph drawing tools because they become too slow for an interactive analysis of the networks and because they produce cluttered drawings with many edge crossings.

Results: A new layout algorithm with complexity management operations in visualizing a large-scale protein interaction network was developed and implemented in a program called InterViewer3. InterViewer3 simplifies a complex network by collapsing a group of nodes with the same interacting partners into a composite node and by replacing a clique with a star-shaped subgraph. The experimental results demonstrated that InterViewer3 is one order of magnitude faster than the other drawing programs and that its complexity management is successful.

Availability: http://wilab.inha.ac.kr/protein/

Contact: khan@inha.ac.kr

Keywords: protein-protein interaction network, visualization, abstraction

*To whom correspondence should be addressed.
GENIA corpus—a semantically annotated corpus for bio-textmining
Authors: Kim J.-D. , Ohta T. , Tateisi Y. , Tsujii J.
Published: July 2003

Motivation: Natural language processing (NLP) methods are regarded as being useful to raise the potential of text mining from biological literature. The lack of an extensively annotated corpus of this literature, however, causes a major bottleneck for applying NLP techniques. GENIA corpus is being developed to provide reference materials to let NLP techniques work for bio-textmining.

Results: GENIA corpus version 3.0 consisting of 2000 MEDLINE abstracts has been released with more than 400 000 words and almost 100 000 annotations for biological terms.

Availability: GENIA corpus is freely available at http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA

Keywords: Text Mining, Information Extraction, Corpus, Natural Language Processing, Computational Molecular Biology

*To whom correspondence should be addressed.
Predicting phenotype from patterns of annotation
Authors: King Oliver D. , Lee Jeffrey C. , Dudley Aimée M. , Janse Daniel M. , Church George M. , Roth Frederick P.
Published: July 2003

Motivation:Predicting the outcome of specific experiments (such as the growth of a particular mutant strain in a particular medium) has the potential to allow researchers to devote resources to experiments with higher expected numbers of ‘hits’.

Results: We use decision trees to predict phenotypes associated with Saccharomyces cerevisiae genes on the basis of Gene Ontology (GO) functional annotations from the Saccharomyces Genome Database (SGD) and other phenotypic annotations from the Yeast Phenotype Catalog at the Munich Information Center for Protein Sequences (MIPS). We assess the methodology in three ways: (1) we use cross-validation on the phenotypic annotations listed in MIPS, and show ROC curves indicating the tradeoff between true-positive rate and false-positive rate; (2) we do a literature-search for 100 of the predicted gene-phenotype associations that are not listed in MIPS, and find evidence for 43 of them; (3) we use deletion strains to experimentally assess 61 predicted gene-phenotype associations not listed in MIPS; significantly more of these deletion strains show abnormal growth than would be expected by chance.

Contact: fritz_roth@hms.harvard.edu

Supplementary Information: Complete results are available at http://llama.med.harvard.edu/~king/pheno.html

Keywords: decision trees; phenotype; gene function

*To whom correspondence should be addressed.
Detection and validation of single gene inversions
Authors: Lefebvre J.F. , El-Mabrouk N. , Tillier E. , Sankoff D.
Published: July 2003

Motivation: The biologically meaningful algorithmic study of genome rearrangement should take into account the distribution of sizes of the rearranged genomic fragments. In particular, it is important to know the prevalence of short inversions in order to understand the patterns of gene order disruption observed in comparative genomics.

Results: We find a large excess of short inversions, especially those involving a single gene, in comparison with a random inversion model. This is demonstrated through comparison of four pairs of bacterial genomes, using a specially-designed implementation of the Hannenhalli–Pevzner theory, and validated through experimentation on pairs of random genomes matched to the real pairs.

Availability: The main routines of the experimental software are available through consultation with the authors.

Contact: sankoff@uottawa.ca

Keywords: short inversions, reversals, genome rearrangement, genome evolution, comparative genomics, bacterial genomes, Hannenhalli--Pevzner algorithm, experimental algorithmics.

*To whom correspondence should be addressed.
Predicting protein function from protein/protein
interaction data: a probabilistic approach
Authors: Letovsky Stanley , Kasif Simon
Published: July 2003

Motivation:The development of experimental methods for genome scale analysis of molecular interaction networks has made possible new approaches to inferring protein function. This paper describes a method of assigning functions based on a probabilistic analysis of graph neighborhoods in a protein-protein interaction network. The method exploits the fact that graph neighbors are more likely to share functions than nodes which are not neighbors. A binomial model of local neighbor function labeling probability is combined with a Markov random field propagation algorithm to assign function probabilities for proteins in the network.

Results: We applied the method to a protein-protein interaction dataset for the yeast Saccharomyces cerevisiae using the Gene Ontology (GO) terms as function labels. The method reconstructed known GO term assignments with high precision, and produced putative GO assignments to 320 proteins that currently lack GO annotation, which represents about 10% of the unlabeled proteins in S. cerevisiae.

Availability: Source code available upon request. Results available athttp://genomics10.bu.edu/netmark

Contact: sletovsky@aol.com

Keywords: protein–protein interaction, protein function prediction, gene ontology, Markov Random fields

*To whom correspondence should be addressed.
An ENSEMBLE machine learning approach for
the prediction of all-alpha membrane proteins
Authors: Martelli Pier Luigi , Fariselli Piero , Casadio Rita
Published: July 2003

Motivation: All-alpha membrane proteins constitute a functionally relevant subset of the whole proteome. Their content ranges from about 10 to 30% of the cell proteins, based on sequence comparison and specific predictive methods. Due to the paucity of membrane proteins solved with atomic resolution, the training/testing sets of predictive methods for protein topography and topology routinely include very few well-solved structures mixed with a hundred proteins known with low resolution. Moreover, available predictors fail in predicting recently crystallised membrane proteins (Chen et al., 2002). Presently the number of well-solved membrane proteins comprises some 59 chains of low sequence homology. It is therefore possible to train/test predictors only with the set of proteins known with atomic resolution and evaluate more thoroughly the performance of different methods.

Results: We implement a cascade-neural network (NN), two different hidden Markov models (HMM), and their ensemble (ENSEMBLE) as a new method. We train and test in cross validation the three methods and ENSEMBLE on the 59 well resolved membrane proteins. ENSEMBLE scores with a per-protein accuracy of 90% for topography and 71% for topology, outperforming the best single method of 7 and 5 percentage points, respectively. When tested on a low resolution set of 151 proteins, with no homology with the 59 proteins, the per-protein accuracy of ENSEMBLE is 76% for topography and 68% for topology. Our results also indicate that the performance of ENSEMBLE is higher than that of the best predictors presently available on the Web.

Contact: gigi@biocomp.unibo.it; http://www.biocomp.unibo.it

*To whom correspondence should be addressed.
APDB: a novel measure for benchmarking sequence
alignment methods without reference alignments
Authors: O’Sullivan Orla , Zehnder Mark , Higgins Des , Bucher Philipp , Grosdidier Aurelien , Notredame Cédric
Published: July 2003

Motivation: We describe APDB, a novel measure for evaluating the quality of a protein sequence alignment, given two or more PDB structures. This evaluation does not require a reference alignment or a structure superposition. APDB is designed to efficiently and objectively benchmark multiple sequence alignment methods.

Results: Using existing collections of reference multiple sequence alignments and existing alignment methods, we show that APDB gives results that are consistent with those obtained using conventional evaluations. We also show that APDB is suitable for evaluating sequence alignments that are structurally equivalent. We conclude that APDB provides an alternative to more conventional methods used for benchmarking sequence alignment packages.

Availability: APDB is implemented in C, its source code and its documentation are available for free on request from the authors.

Contact: cedric.notredame@europe.com

*To whom correspondence should be addressed.
GeneLoc: exon-based integration of human genome maps
Authors: Rosen Naomi , Chalifa-Caspi Vered , Shmueli Orit , Adato Avital , Lapidot Michal , Stampnitzky Julie , Safran Marilyn , Lancet Doron
Published: July 2003

Motivation:Despite the numerous available whole-genome mapping resources, no comprehensive, integrated map of the human genome yet exists.

Results: GeneLoc, software adjunct to GeneCards and UDB, integrates gene lists by comparing genomic coordinates at the exon level and assigns unique and meaningful identifiers to each gene.

Availability: http://bioinfo.weizmann.ac.il/genecards and http://genecards.weizmann.ac.il/udb

Supplementary information: http://bioinfo.weizmann.ac.il/cards-bin/AboutGCids.cgi, http://genecards.weizmann.ac.il/GeneLocAlg.html

Contact: marilyn.safran@weizmann.ac.il

*To whom correspondence should be addressed.
The discovery net system for high throughput bioinformatics
Authors: Rowe Anthony , Kalaitzopoulos Dimitrios , Osmond Michelle , Ghanem Moustafa , Guo Yike
Published: July 2003

Motivation: Bioinformatics requires Grid technologies and protocols to build high performance applications without focusing on the low level detail of how the individual Grid components operate.

Results: The Discovery Net system is a middleware that allows service developers to integrate tools based on existing and emerging Grid standards such as web services. Once integrated, these tools can be used to compose reusable workflows using these services that can later be deployed as new services for others to use. Using the Discovery Net system and a range of different bioinformatics tools, we built a Grid based application for Genome Annotation. This includes workflows for automatic nucleotide annotation, annotation of predicted proteins and text analysis based on metabolic profiles and text analysis.

Contact: asr99@doc.ic.ac.uk

Keywords: grid, E-Science, annotation, workflow, pipeline.

*To whom correspondence should be addressed.
Pair hidden Markov models on tree structures
Authors: Sakakibara Yasubumi
Published: July 2003

Motivation: Computationally identifying non-coding RNA regions on the genome has much scope for investigation and is essentially harder than gene-finding problems for protein-coding regions. Since comparative sequence analysis is effective for non-coding RNA detection, efficient computational methods are expected for structural alignments of RNA sequences. On the other hand, Hidden Markov Models (HMMs) have played important roles for modeling and analysing biological sequences. Especially, the concept of Pair HMMs (PHMMs) have been examined extensively as mathematical models for alignments and gene finding.

Results: We propose the pair HMMs on tree structures (PHMMTSs), which is an extension of PHMMs defined on alignments of trees and provides a unifying framework and an automata-theoretic model for alignments of trees, structural alignments and pair stochastic context-free grammars. By structural alignment, we mean a pairwise alignment to align an unfolded RNA sequence into an RNA sequence of known secondary structure. First, we extend the notion of PHMMs defined on alignments of ‘linear’ sequences to pair stochastic tree automata, called PHMMTSs, defined on alignments of ‘trees’. The PHMMTSs provide various types of alignments of trees such as affine-gap alignments of trees and an automata-theoretic model for alignment of trees. Second, based on the observation that a secondary structure of RNA can be represented by a tree, we apply PHMMTSs to the problem of structural alignments of RNAs. We modify PHMMTSs so that it takes as input a pair of a ‘linear’ sequence and a ‘tree’ representing a secondary structure of RNA to produce a structural alignment. Further, the PHMMTSs with input of a pair of two linear sequences is mathematically equal to the pair stochastic context-free grammars. We demonstrate some computational experiments to show the effectiveness of our method for structural alignments, and discuss a complexity issue of PHMMTSs.

Contact: yasu@bio.keio.ac.jp

Keywords: hidden Markov model, tree automaton, structural alignment, stochastic context-free grammar, RNA, secondary structure.