Cancer is a rapidly evolving disease, with complex physiological changes throughout its development. Different patients of the same cancer type may require distinct treatments depending on the level of development. Hence it is essential to identify the genes and biological processes strongly associated with cancer progression to design an effective treatment plan. Our study has found that cancer samples of the same development stage (or grade, subtype) tend to share highly unique co-expression patterns, providing considerably stronger discerning power than differential expressions for cancer staging (and grading, subtyping). Based on this, we have developed a framework for identification and analyses of genes and pathways strongly associated with a cancer's development through identification of co-expression patterns that become increasingly stronger or weaker over cancer samples from early through advanced stages. Functional analyses of such co-expressed genes reveal that (1) cell-cycle, immune response, ribosome, proteasome and oxidative phosphorylation, among others, strongly associate with cancer development, (2) the co-expression patterns among ribosome, proteasome and oxidative phosphorylation genes tend to become increasingly weaker as a cancer advances, for almost all cancer types, and (3) the co-expression patterns among cell cycle and immune response genes tend to become increasingly stronger with cancer progression. We anticipate that co-expression-based analyses like we present here will become a key technique for functional studies of cancer development and evolution.

High-throughput sequencing of mRNA has made the deep and efficient probing of transcriptome more affordable. However, the vast amounts of short RNA-seq reads make de novo transcriptome assembly an algorithmic challenge. In this work, we present IsoTree, a novel framework for transcripts reconstruction in the absence of reference genomes. Unlike most of de novo assembly methods that build de Bruijn graph or splicing graph by connecting k- mers which are sets of overlapping substrings generated from reads, IsoTree constructs splicing graph by connecting reads directly. For each splicing graph, IsoTree applies an iterative scheme of mixed integer linear program to build a prefix tree, called isoform tree. Each path from the root node of the isoform tree to a leaf node represents a plausible transcript candidate which will be pruned based on the information of paired-end reads. Experiments showed that in most cases IsoTree performs better than other leading transcriptome assembly programs. IsoTree is available at https://github.com/Jane110111107/IsoTree.

Presents corrections to author information in the above named paper.

Cancer staging, grading and subtyping all represent important problems for precision diagnosis, treatment and mechanistic studies of cancer. The majority of the existing computational methods solve this problem via multi-classification of differential gene-expressions of cancer samples of specific classes (Stages, Grades and subtypes) vs. controls. However, the performance of such classification techniques is generally not satisfactory since the discerning power of differential expression patterns in such classifications is limited. We present here a multi-classification technique, based on co-expression patterns specific to individual subclasses in provided training data as co-expression patterns tend to be more conserved than differential expressions within each subclass. A challenge in implementing this strategy lies in how to effectively derive co-expression patterns in individual samples, which is solved through comparing co-expression patterns within a subclass and those in the subclass plus a new sample. Compared with the state-of-the-art gene expression-based classification methods, our method outperforms them in cancer staging, grading and subtyping of cancer samples from TCGA in almost all the measures used. In addition, the co-expressed genes computationally selected for classifications are biologically meaningful, which will prove important for diagnostic biomarker design, treatment plan selection and possibly mechanistic studies of cancer.

The rapid accumulation of fully sequenced prokaryotic genomes provides unprecedented information for biological studies of bacterial and archaeal organisms in a systematic manner. Operons are the basic functional units for conducting such studies. Here, we review an operon database DOOR (the Database of prOkaryotic OpeRons) that we have previously developed and continue to update. Currently, the database contains 6 975 454 computationally predicted operons in 2072 complete genomes. In addition, the database also contains the following information: (i) transcriptional units for 24 genomes derived using publicly available transcriptomic data; (ii) orthologous gene mapping across genomes; (iii) 6408 cis-regulatory motifs for transcriptional factors of some operons for 203 genomes; (iv) 3 456 718 Rho-independent terminators for 2072 genomes; as well as (v) a suite of tools in support of applications of the predicted operons. In this review, we will explain how such data are computationally derived and demonstrate how they can be used to derive a wide range of higher-level information needed for systems biology studies to tackle complex and fundamental biology questions.

We present here an integrated analysis of structures and functions of genome-scale metabolic networks of 17 microorganisms. Our structural analyses of these networks revealed that the node degree of each network, represented as a (simplified) reaction network, follows a power-law distribution, and the clustering coefficient of each network has a positive correlation with the corresponding node degree. Together, these properties imply that each network has exactly one large and densely connected subnetwork or core. Further analyses revealed that each network consists of three functionally distinct subnetworks: (i) a core, consisting of a large number of directed reaction cycles of enzymes for interconversions among intermediate metabolites; (ii) a catabolic module, with a largely layered structure consisting of mostly catabolic enzymes; (iii) an anabolic module with a similar structure consisting of virtually all anabolic genes; and (iv) the three subnetworks cover on average ∼56, ∼31 and ∼13% of a network's nodes across the 17 networks, respectively. Functional analyses suggest: (1) cellular metabolic fluxes generally go from the catabolic module to the core for substantial interconversions, then the flux directions to anabolic module appear to be determined by input nutrient levels as well as a set of precursors needed for macromolecule syntheses; and (2) enzymes in each subnetwork have characteristic ranges of kinetic parameters, suggesting optimized metabolic and regulatory relationships among the three subnetworks.

BACKGROUND: Alternative splicing allows the pre-mRNAs of a gene to be spliced into various mRNAs, which greatly increases the diversity of proteins. High-throughput sequencing of mRNAs has revolutionized our ability for transcripts reconstruction. However, the massive size of short reads makes de novo transcripts assembly an algorithmic challenge. RESULTS: We develop a novel radical framework, called DTA-SiST, for de novo transcriptome assembly based on suffix trees. DTA-SiST first extends contigs by reads that have the longest overlaps with the contigs' terminuses. These reads can be found in linear time of the lengths of the reads through a well-designed suffix tree structure. Then, DTA-SiST constructs splicing graphs based on contigs for each gene locus. Finally, DTA-SiST proposes two strategies to extract transcript-representing paths: a depth-first enumeration strategy and a hybrid strategy based on length and coverage. We implemented the above two strategies and compared them with the state-of-the-art de novo assemblers on both simulated and real datasets. Experimental results showed that the depth-first enumeration strategy performs always better with recall and also better with precision for smaller datasets while the hybrid strategy leads with precision for big datasets. CONCLUSIONS: DTA-SiST performs more competitive than the other compared de novo assemblers especially with precision measure, due to the read-based contig extension strategy and the elegant transcripts extraction rules.

Due to the excellent advantages of high speed and high precision, fast tool servo (FTS) system driven by piezoelectric actuators has great attraction for high-quality machining of microstructural array. However, its complex hysteresis nonlinearity at high speed will greatly affect the accuracy and stability of FTS system. Therefore, a stable autoregressive moving average (SARMA) model is proposed in this paper, which aims to describe the dynamic hysteresis nonlinearity accurately. First, a long autoregressive model residual calculation method is used to determine the order of the model and test the applicability of the model. Then, according to the Lyapunov stability theory, the strict stability analysis of the autoregressive moving average (ARMA) model is carried out in theory. By introducing the relaxation factor to transform the stability condition, the Lagrange multiplier and best square approximation method are applied to enhance the performance of the traditional ARMA model. Aiming at the difficulty of displacement sensor integration in FTS closed-loop controlling system, a hysteresis-compensated direct feedforward control strategy based on the proposed SARMA model is designed. Finally, a series of high-frequency trajectory tracking and comparing experiments has been carried out successfully with the traditional Prandtl-Ishlinskii (PI) and SARMA models to verify the effectiveness and superiority of the method. All results uniformly indicate that the SARMA model is nearly 20 times higher than the traditional PI model in terms of control accuracy and linearity, while the average linearity of FTS's dynamic tracking control is kept within 0.43% (265 nm), the stroke is 280 μm, and the positioning bandwidth is achieved up to 200 Hz.

In this paper, we develop a novel graph theoretic approach for protein threading. In order to perform the protein sequence-structure alignment in threading both efficiently and accurately, we develop a graph model to describe the tertiary structure of a protein family and the alignment between a sequence and a family can be efficiently computed with a dynamic programming algorithm when the tree width of the graph model is a small integer. Our experiments show that this new approach is significantly faster than existing tools for threading and can achieve comparable prediction accuracy.

BACKGROUND: Bacterial operons are considerably more complex than what were thought. At least their components are dynamically rather than statically defined as previously assumed. Here we present a computational study of the landscape of the transcriptional units (TUs) of E. coli K12, revealed by the available genomic and transcriptomic data, providing new understanding about the complexity of TUs as a whole encoded in the genome of E. coli K12. RESULTS AND CONCLUSION: Our main findings include that (i) different TUs may overlap with each other by sharing common genes, giving rise to clusters of overlapped TUs (TUCs) along the genomic sequence; (ii) the intergenic regions in front of the first gene of each TU tend to have more conserved sequence motifs than those of the other genes inside the TU, suggesting that TUs each have their own promoters; (iii) the terminators associated with the 3' ends of TUCs tend to be Rho-independent terminators, substantially more often than terminators of TUs that end inside a TUC; and (iv) the functional relatedness of adjacent gene pairs in individual TUs is higher than those in TUCs, suggesting that individual TUs are more basic functional units than TUCs.

Presents an editorial for this issue of the publication.

The success of RNA interference (RNAi) depends on the interaction between short interference RNAs (siRNAs) and mRNAs. Design of highly efficient and specific siRNAs has become a challenging issue in applications of RNAi. Here, we present a detailed survey on the state-of-the-art siRNAs design, focusing on several key issues with the current in silico RNAi studies, including: (i) inconsistencies among the proposed guidelines for siRNAs design and the incomplete list of siRNAs features, (ii) improper integration of the heterogeneous cross-platform siRNAs data, (iii) inadequate consideration of the binding specificity of the target mRNAs and (iv) reduction in the 'off-target' effect in siRNAs design. With these considerations, the popular in silico siRNAs design rules are reexamined and several inconsistent viewpoints toward siRNAs feature identifications are clarified. In addition, novel computational models for siRNAs design using state-of-art machine learning techniques are discussed, which focus on heterogeneous data integration, joint feature selection and customized siRNAs screening toward highly specific targets. We believe that addressing such issues in siRNA study will provide new clues for further improved design of more efficient and specific siRNAs in RNAi.

The EiC reviews his first year of serving as the Editor-in-Chief (EIC) of the IEEE/ACM Transactions on Computational Biology and Bioinformatics. In 2013, two new columns were started in the journal, one on visionary perspectives by lead authors of the field and one on bioinformatics software tools and databases. Last year, TCBB received a total of 419 submissions, and published 139 papers, including 30 best papers selected from six bioinformatics conferences. Seventeen new associate editors joined the Editorial Board of TCBB in 2013. They were Professor Pierre Baldi of UC Irvine, Professor Graziano Chesi of Hongkong University, Professor Charlie Hodgman of the University of Nottingham, Professor Vasant Honavar of Penn State University, Dr. Suzanna Lewis of Lawrence Berkley National Lab, Professor Tianming Liu of the University of Georgia, Professor Yixue Li of the Chinese Academy of Sciences - Shanghai, Professor Michael Lutz of Duke University, Professor Bin Ma of Waterloo University, Dr. Sergei Maslov of Brookhaven National Lab, Professor Jason Moore of Dartmouth College, Professor Sanjay Ranka of the University of Florida, Professor Haixu Tang of Indiana University, Professor Yufeng Wu of the University of Connecticut, Professor Dong Xu of the University of Missouri, Professor Ming Zhan of The Methodist Hospital Research Institute, and Professor Yang Zhang of the University of Michigan. Among them, Professor Dong Xu was appointed as the Associate Editor-in-Chief in charge of special issues in the journal. Biographies for these associate editors are provided.

The publication offers a note of thanks and lists its reviewers.

In this talk, I will present our recent work on how inflammation, change in the availability of oxygen, and hyaluronan play essential roles in key transitions in cancer development, including initiation and metastasis.

MOTIVATION: We present an integrated toolkit, BoBro2.0, for prediction and analysis of cis-regulatory motifs. This toolkit can (i) reliably identify statistically significant cis-regulatory motifs at a genome scale; (ii) accurately scan for all motif instances of a query motif in specified genomic regions using a novel method for P-value estimation; (iii) provide highly reliable comparisons and clustering of identified motifs, which takes into consideration the weak signals from the flanking regions of the motifs; and (iv) analyze co-occurring motifs in the regulatory regions. RESULTS: We have carried out systematic comparisons between motif predictions using BoBro2.0 and the MEME package. The comparison results on Escherichia coli K12 genome and the human genome show that BoBro2.0 can identify the statistically significant motifs at a genome scale more efficiently, identify motif instances more accurately and get more reliable motif clusters than MEME. In addition, BoBro2.0 provides correlational analyses among the identified motifs to facilitate the inference of joint regulation relationships of transcription factors. AVAILABILITY: The source code of the program is freely available for noncommercial uses at http://code.google.com/p/bobro/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

I would like to take this opportunity to sincerely thank the TCBB Steering Committee for the trust and opportunity it has given me to serve as the new Editor-in-Chief of the journal. I am really excited about all the possibilities that I can explore through working with the excellent Editorial Board, the Steering Committee, and the Computer Society staff, to help the journal continue to grow. I also recognize that I have very big shoes to fill, knowing the fantastic jobs that my predecessors Professor Dan Gusfield and Professor Marie-France Sagot have done since the founding of the journal in 2004. I was trained as a theoretical computer scientist and am now working in a biochemistry and molecular biology department. I hope that I can help to build stronger ties between the journal and a larger biological community, striving to make TCBB a leading resource for biologists to check out first when they search for the most useful computational techniques and tools to handle their data analysis and computational prediction and modeling needs. Biology is becoming increasingly more quantitative fueled by the rapid and continued emergence of new omic techniques. The availability of such data has made it possible for biologists to ask broader and deeper questions about more complex biological systems. It clearly requires increasingly more powerful techniques and tools to derive all the information hidden in the large quantities of the omic data and to facilitate the full utilization of the information in addressing specific biological questions. This is a really great time for computational biologists and bioinformaticians, as the needs for such people are tremendous. TCBB can clearly play a key role in helping the transition of biology to become a more quantitative science built on fundamental principles and laws. I plan to bring in additional editorial board members whose expertise will be complementary to that of the current board members, to better position the journal to attract and handle submissions in the emerging areas of bioinformatics and computational biology, mostly driven by the emergence of new omic techniques. I also aim to establish a new column for review articles to better inform the community associated with the TCBB about the new data and computational needs and challenges from different areas of biology, helping to make the information flow both ways efficiently. I am also looking forward to hearing suggestions and advice from the readers, authors, and the editorial board members of the journal, which can help to move TCBB to the next level, based on the superb foundation that Professor Dan Gusfield and Professor Marie-France Sagot have laid. I look forward to working and interacting with you!

BACKGROUND: The frequent exchange of genetic material among prokaryotes means that extracting a majority or plurality phylogenetic signal from many gene families, and the identification of gene families that are in significant conflict with the plurality signal is a frequent task in comparative genomics, and especially in phylogenomic analyses. Decomposition of gene trees into embedded quartets (unrooted trees each with four taxa) is a convenient and statistically powerful technique to address this challenging problem. This approach was shown to be useful in several studies of completely sequenced microbial genomes. RESULTS: We present here a web server that takes a collection of gene phylogenies, decomposes them into quartets, generates a Quartet Spectrum, and draws a split network. Users are also provided with various data download options for further analyses. Each gene phylogeny is to be represented by an assessment of phylogenetic information content, such as sets of trees reconstructed from bootstrap replicates or sampled from a posterior distribution. The Quartet Decomposition server is accessible at http://quartets.uga.edu. CONCLUSIONS: The Quartet Decomposition server presented here provides a convenient means to perform Quartet Decomposition analyses and will empower users to find statistically supported phylogenetic conflicts.

BACKGROUND: Reconstruction of biological pathways is typically done through mapping well-characterized pathways of model organisms to a target genome, through orthologous gene mapping. A limitation of such pathway-mapping approaches is that the mapped pathway models are constrained by the composition of the template pathways, e.g., some genes in a target pathway may not have corresponding genes in the template pathways, the so-called "missing gene" problem. METHODS: We present a novel pathway-expansion method for identifying additional genes that are possibly involved in a target pathway after pathway mapping, to fill holes caused by missing genes as well as to expand the mapped pathway model. The basic idea of the algorithm is to identify genes in the target genome whose homologous genes share common operons with homologs of any mapped pathway genes in some reference genome, and to add such genes to the target pathway if their functions are consistent with the cellular function of the target pathway. RESULTS: We have implemented this idea using a graph-theoretic approach and demonstrated the effectiveness of the algorithm on known pathways of E. coli in the KEGG database. On all KEGG pathways containing at least 5 genes, our method achieves an average of 60% positive predictive value (PPV) and the performance is increased with more seed genes added. Analysis shows that our method is highly robust. CONCLUSIONS: An effective method is presented to find missing genes in biological pathways of prokaryotes, which achieves high prediction reliability on E. coli at a genome level. Numerous missing genes are found to be related to known E. coli pathways, which can be further validated through biological experiments. Overall this method is robust and can be used for functional inference.

SUMMARY: Huge amount of metagenomic sequence data have been produced as a result of the rapidly increasing efforts worldwide in studying microbial communities as a whole. Most, if not all, sequenced metagenomes are complex mixtures of chromosomal and plasmid sequence fragments from multiple organisms, possibly from different kingdoms. Computational methods for prediction of genomic elements such as genes are significantly different for chromosomes and plasmids, hence raising the need for separation of chromosomal from plasmid sequences in a metagenome. We present a program for classification of a metagenome set into chromosomal and plasmid sequences, based on their distinguishing pentamer frequencies. On a large training set consisting of all the sequenced prokaryotic chromosomes and plasmids, the program achieves approximately 92% in classification accuracy. On a large set of simulated metagenomes with sequence lengths ranging from 300 bp to 100 kbp, the program has classification accuracy from 64.45% to 88.75%. On a large independent test set, the program achieves 88.29% classification accuracy. AVAILABILITY: The program has been implemented as a standalone prediction program, cBar, which is available at http://csbl.bmb.uga.edu/~ffzhou/cBar.

BACKGROUND: Computational identification of blood-secretory proteins, especially proteins with differentially expressed genes in diseased tissues, can provide highly useful information in linking transcriptomic data to proteomic studies for targeted disease biomarker discovery in serum. RESULTS: A new algorithm for prediction of blood-secretory proteins is presented using an information-retrieval technique, called manifold ranking. On a dataset containing 305 known blood-secretory human proteins and a large number of other proteins that are either not blood-secretory or unknown, the new method performs better than the previous published method, measured in terms of the area under the recall-precision curve (AUC). A key advantage of the presented method is that it does not explicitly require a negative training set, which could often be noisy or difficult to derive for most biological problems, hence making our method more applicable than classification-based data mining methods in general biological studies. CONCLUSION: We believe that our program will prove to be very useful to biomedical researchers who are interested in finding serum markers, especially when they have candidate proteins derived through transcriptomic or proteomic analyses of diseased tissues. A computer program is developed for prediction of blood-secretory proteins based on manifold ranking, which is accessible at our website http://csbl.bmb.uga.edu/publications/materials/qiliu/blood_secretory_protein.html.

The problem of sorting by reciprocal translocations (abbreviated as SBT) arises from the field of comparative genomics, which is to find a shortest sequence of reciprocal translocations that transforms one genome Pi into another genome Gamma, with the restriction that Pi and Gamma contain the same genes. SBT has been proved to be polynomial-time solvable, and several polynomial algorithms have been developed. In this paper, we show how to extend Bergeron's SBT algorithm to include insertions and deletions, allowing to compare genomes containing different genes. In particular, if the gene set of Pi is a subset (or superset, respectively) of the gene set of Gamma, we present an approximation algorithm for transforming Pi into Gamma by reciprocal translocations and deletions (insertions, respectively), providing a sorting sequence with length at most OPT + 2, where OPT is the minimum number of translocations and deletions (insertions, respectively) needed to transform Pi into Gamma; if Pi and Gamma have different genes but not containing each other, we give a heuristic to transform Pi into Gamma by a shortest sequence of reciprocal translocations, insertions, and deletions, with bounds for the length of the sorting sequence it outputs. At a conceptual level, there is some similarity between our algorithm and the algorithm developed by El Mabrouk which is used to sort two chromosomes with different gene contents by reversals, insertions, and deletions.

MOTIVATION: The computational identification of non-coding RNA (ncRNA) genes represents one of the most important and challenging problems in computational biology. Existing methods for ncRNA gene prediction rely mostly on homology information, thus limiting their applications to ncRNA genes with known homologues. RESULTS: We present a novel de novo prediction algorithm for ncRNA genes using features derived from the sequences and structures of known ncRNA genes in comparison to decoys. Using these features, we have trained a neural network-based classifier and have applied it to Escherichia coli and Sulfolobus solfataricus for genome-wide prediction of ncRNAs. Our method has an average prediction sensitivity and specificity of 68% and 70%, respectively, for identifying windows with potential for ncRNA genes in E.coli. By combining windows of different sizes and using positional filtering strategies, we predicted 601 candidate ncRNAs and recovered 41% of known ncRNAs in E.coli. We experimentally investigated six novel candidates using Northern blot analysis and found expression of three candidates: one represents a potential new ncRNA, one is associated with stable mRNA decay intermediates and one is a case of either a potential riboswitch or transcription attenuator involved in the regulation of cell division. In general, our approach enables the identification of both cis- and trans-acting ncRNAs in partially or completely sequenced microbial genomes without requiring homology or structural conservation. AVAILABILITY: The source code and results are available at http://csbl.bmb.uga.edu/publications/materials/tran/.

BACKGROUND: Understanding the constituent domains of oncogenes, their origins and their fusions may shed new light about the initiation and the development of cancers. RESULTS: We have developed a computational pipeline for identification of functional domains of human genes, prediction of the origins of these domains and their major fusion events during evolution through integration of existing and new tools of our own. An application of the pipeline to 124 well-characterized human oncogenes has led to the identification of a collection of domains and domain pairs that occur substantially more frequently in oncogenes than in human genes on average. Most of these enriched domains and domain pairs are related to tyrosine kinase activities. In addition, our analyses indicate that a substantial portion of the domain-fusion events of oncogenes took place in metazoans during evolution. CONCLUSION: We expect that the computational pipeline for domain identification, domain origin and domain fusion prediction will prove to be useful for studying other groups of genes.

We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized. The minimum congestion hypergraph embedding in a cycle problem is known to be NP-hard and its graph version, the minimum congestion graph embedding in a cycle , is solvable in polynomial-time. Furthermore, for the graph problem, a polynomial-time approximation scheme for the weighted version is known. For the hypergraph model, several approximation algorithms with a ratio of two have been previously published. A recent paper reduced the approximation ratio to 1.5. We present a polynomial-time approximation scheme in this article, settling the debate regarding whether the problem is polynomial-time approximable.

Large sets of bioinformatical data provide a challenge in time consumption while solving the cluster identification problem, and that is why a parallel algorithm is so needed for identifying dense clusters in a noisy background. Our algorithm works on a graph representation of the data set to be analyzed. It identifies clusters through the identification of densely intraconnected subgraphs. We have employed a minimum spanning tree (MST) representation of the graph and solve the cluster identification problem using this representation. The computational bottleneck of our algorithm is the construction of an MST of a graph, for which a parallel algorithm is employed. Our high-level strategy for the parallel MST construction algorithm is to first partition the graph, then construct MSTs for the partitioned subgraphs and auxiliary bipartite graphs based on the subgraphs, and finally merge these MSTs to derive an MST of the original graph. The computational results indicate that when running on 150 CPUs, our algorithm can solve a cluster identification problem on a data set with 1,000,000 data points almost 100 times faster than on single CPU, indicating that this program is capable of handling very large data clustering problems in an efficient manner. We have implemented the clustering algorithm as the software CLUMP.

We present a novel computational method for predicting which proteins from highly and abnormally expressed genes in diseased human tissues, such as cancers, can be secreted into the bloodstream, suggesting possible marker proteins for follow-up serum proteomic studies. A main challenging issue in tackling this problem is that our understanding about the downstream localization after proteins are secreted outside the cells is very limited and not sufficient to provide useful hints about secretion to the bloodstream. To bypass this difficulty, we have taken a data mining approach by first collecting, through extensive literature searches, human proteins that are known to be secreted into the bloodstream due to various pathological conditions as detected by previous proteomic studies, and then asking the question: 'what do these secreted proteins have in common in terms of their physical and chemical properties, amino acid sequence and structural features that can be used to predict them?' We have identified a list of features, such as signal peptides, transmembrane domains, glycosylation sites, disordered regions, secondary structural content, hydrophobicity and polarity measures that show relevance to protein secretion. Using these features, we have trained a support vector machine-based classifier to predict protein secretion to the bloodstream. On a large test set containing 98 secretory proteins and 6601 non-secretory proteins of human, our classifier achieved approximately 90% prediction sensitivity and approximately 98% prediction specificity. Several additional datasets are used to further assess the performance of our classifier. On a set of 122 proteins that were found to be of abnormally high abundance in human blood due to various cancers, our program predicted 62 as blood-secreted proteins. By applying our program to abnormally highly expressed genes in gastric cancer and lung cancer tissues detected through microarray gene expression studies, we predicted 13 and 31 as blood secreted, respectively, suggesting that they could serve as potential biomarkers for these two cancers, respectively. Our study demonstrated that our method can provide highly useful information to link genomic and proteomic studies for disease biomarker discovery. Our software can be accessed at http://csbl1.bmb.uga.edu/cgi-bin/Secretion/secretion.cgi.

BACKGROUND: Each genome has a stable distribution of the combined frequency for each k-mer and its reverse complement measured in sequence fragments as short as 1000 bps across the whole genome, for 1<k<6. The collection of these k-mer frequency distributions is unique to each genome and termed the genome's barcode. RESULTS: We found that for each genome, the majority of its short sequence fragments have highly similar barcodes while sequence fragments with different barcodes typically correspond to genes that are horizontally transferred or highly expressed. This observation has led to new and more effective ways for addressing two challenging problems: metagenome binning problem and identification of horizontally transferred genes. Our barcode-based metagenome binning algorithm substantially improves the state of the art in terms of both binning accuracies and the scope of applicability. Other attractive properties of genomes barcodes include (a) the barcodes have different and identifiable characteristics for different classes of genomes like prokaryotes, eukaryotes, mitochondria and plastids, and (b) barcodes similarities are generally proportional to the genomes' phylogenetic closeness. CONCLUSION: These and other properties of genomes barcodes make them a new and effective tool for studying numerous genome and metagenome analysis problems.

Identifying operons at the whole genome scale of microbial organisms can facilitate deciphering of transcriptional regulation, biological networks and pathways. A number of computational methods, such as naive Bayesian and neural network approaches, have been employed for operon prediction to whole genome sequences of a number of prokaryotic organisms, based on features known to be associated with operons, such as intergenic distance, microarray expression data, phylogenetic profiles, clusters of orthologous groups (COG). In this paper, we introduce a decision tree approach to predict operon structures using three effective types of genomic data: intergenic distance, gene order conservation and COG. We calculated and analyzed frequency distributions of each attribute of known operons and non-operons of Escherichia coli (E. coli) K12 and Bacillus subtilis (R subtilis) 168, and constructed decision trees based on training examples to predict operons. The overall prediction accuracy is 94.1% for E. coli K12 and 91.0% for B. subtilis 168. We also applied four other classifiers, logistic regression, naive Bayesian, neural network and support vector machines on both organisms. The results indicate that the decision tree approach is the best classifier for operon prediction. The software package operonDT is freely available at http://www.cs.uga.edn/~che/OperonT

UNLABELLED: Palmitoylation is an important post-translational lipid modification of proteins. Unlike prenylation and myristoylation, palmitoylation is a reversible covalent modification, allowing for dynamic regulation of multiple complex cellular systems. However, in vivo or in vitro identification of palmitoylation sites is usually time-consuming and labor-intensive. So in silico predictions could help to narrow down the possible palmitoylation sites, which can be used to guide further experimental design. Previous studies suggested that there is no unique canonical motif for palmitoylation sites, so we hypothesize that the bona fide pattern might be compromised by heterogeneity of multiple structural determinants with different features. Based on this hypothesis, we partition the known palmitoylation sites into three clusters and score the similarity between the query peptide and the training ones based on BLOSUM62 matrix. We have implemented a computer program for palmitoylation site prediction, Clustering and Scoring Strategy for Palmitoylation Sites Prediction (CSS-Palm) system, and found that the program's prediction performance is encouraging with highly positive Jack-Knife validation results (sensitivity 82.16% and specificity 83.17% for cut-off score 2.6). Our analyses indicate that CSS-Palm could provide a powerful and effective tool to studies of palmitoylation sites. AVAILABILITY: CSS-Palm is implemented in PHP/PERL+MySQL and can be freely accessed at http://bioinformatics.lcd-ustc.org/css_palm/ CONTACT: [email protected]; [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bionformatics online.

Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity, but also spatially conserved conformations caused by residue interactions and, consequently, is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where, in general, the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O[k(t)N(2)] for the structure of N residues and its tree decomposition of width t. Parameter k, small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. This paper demonstrates a successful application of the algorithm to RNA structure search used for noncoding RNA identification. An application to protein threading is also discussed.

MOTIVATION: Ion-type identification is a fundamental problem in computational proteomics. Methods for accurate identification of ion types provide the basis for many mass spectrometry data interpretation problems, including (a) de novo sequencing, (b) identification of post-translational modifications and mutations and (c) validation of database search results. RESULTS: Here, we present a novel graph-theoretic approach for solving the problem of separating b ions from y ions in a set of tandem mass spectra. We represent each spectral peak as a node and consider two types of edges: type-1 edge connecting two peaks probably of the same ion types and type-2 edge connecting two peaks probably of different ion types. The problem of ion-separation is formulated and solved as a graph partition problem, which is to partition the graph into three subgraphs, representing b, y and others ions, respectively, through maximizing the total weight of type-1 edges while minimizing the total weight of type-2 edges within each partitioned subgraph. We have developed a dynamic programming algorithm for rigorously solving this graph partition problem and implemented it as a computer program PRIME (PaRtition of Ion types in tandem Mass spEctra). The tests on a large amount of simulated mass spectra and 19 sets of high-quality experimental Fourier transform ion cyclotron resonance tandem mass spectra indicate that an accuracy level of approximately 90% for the separation of b and y ions was achieved. AVAILABILITY: The executable code of PRIME is available upon request. CONTACT: [email protected].

We have recently developed a computational capability for (a) inference of individual response networks and (b) global transcription regulation networks in Synechococcus sp. WH8102. The overall framework for inference of response networks can be summarized as follows. The framework employs a template-based network inference strategy. Under this framework, we first identify organisms that are known to have similar response systems to Synechococcus sp for a particular stimulus, and that have a large quantity of experimental data available, particularly microarray gene expression data. For each such "template" organism, we first build network models, and then map these template network models to Synechococcus sp. Through literature search and database search, we build a conceptual framework first for a specific response network in each template organism. The detailed network models will be then built through a series of predictions of gene functions, operon and regulon structures, transcription regulatory binding sites, protein-protein interactions and protein-DNA interactions, and incorporate these prediction results into the conceptual model. After the template network models are built, we map these models to Synechococcus sp through a constrained orthologous gene mapping scheme. The basic idea is to map genes of a network model to their predicted homologous genes under the constraints that these genes should belong to a group of co-regulated operons, which is predicted based on operon structure prediction and prediction of transcriptional regulatory binding sites. The mapped network models will then be refined and expanded through application of a genome-scale protein-protein interaction network, which is predicted through a series of computational prediction tools. We have applied this capability to derive a number of response networks in Synechococcus sp, such as phosphorus assimilation pathway, carbon fixation pathway, nitrogen assimilation pathway. Experiments are currently under way to validate these predictions. A major challenge remains in automated mining of literature to extract useful information to build the initial conceptual network to collect information about gene functions and interactions. Prediction of global transcription regulatory network is done through prediction of (a) transcription factors (TF) at genome scale, (b) operon predictions, (c) prediction of TF binding sites for each predicted operon, and (d) prediction of interactions between predicted TFs and TF binding sites. The key techniques we have used for many of these predictions include (i) comparative genome analysis and (ii) computational inference of co-evolution relationships through applications of methods such as phylogenetic profile analysis. Through these predictions, we have identified a number of global transcription regulators and a sequence of transcription regulators responsive to particular stimuli. Interaction relationship between these TFs and the predicted TF binding sites is predicted based on predicted co-evolution relationships of TFs and genes in each predicted operon. A preliminary global network of transcription regulation is predicted.

Characterizing biological pathways at the genome scale is one of the most important and challenging tasks in the post genomic era. To address this challenge, we have developed a computational method to systematically and automatically derive partial biological pathways in yeast using high-throughput biological data, including yeast two hybrid data, protein complexes identified from mass spectroscopy, genetics interactions, and microarray gene expression data in yeast Saccharomyces cerevisiae. The inputs of the method are the upstream starting protein (e.g., a sensor of a signal) and the downstream terminal protein (e.g., a transcriptional factor that induces genes to respond the signal); the output of the method is the protein interaction chain between the two proteins. The high-throughput data are coded into a graph of interaction network, where each node represents a protein. The weight of an edge between two nodes models the "closeness" of the two represented proteins in the interaction network and it is defined by a rule-based formula according to the high-throughput data and modified by the protein function classification and subcellular localization information. The protein interaction cascade pathway in vivo is predicted as the shortest path identified from the graph of the interaction network using Dijkstra's algorithm. We have also developed a web server of this method (http://compbio.ornl.gov/structure/pathway) for public use. To our knowledge, our method is the first automated method to generally construct partial biological pathways using a suite of high-throughput biological data. This work demonstrates the proof of principle using computational approaches for discoveries of biological pathways with high-throughput data and biological annotation data.

Traditionally, protein 3D structures are solved using experimental techniques, like X-ray crystallography or nuclear magnetic resonance (NMR). While these experimental techniques have been the main workhorse for protein structure studies in the past few decades, it is becoming increasingly apparent that they alone cannot keep up with the production rate of protein sequences. Fortunately, computational techniques for protein structure predictions have matured to such a level that they can complement the existing experimental techniques. In this paper, we present an automated pipeline for protein structure prediction. The centerpiece of the pipeline is a threading-based protein structure prediction system, called PROSPECT, which we have been developing for the past few years. The pipeline consists of seven logical phases, utilizing a dozen tools. The pipeline has been implemented to run in a heterogeneous computational environment as a client/server system with a web interface. A number of genome-scale applications have been carried out on microbial genomes. Here we present one genome-scale application on Caenorhabditis elegans.

MOTIVATION: Experimental techniques alone cannot keep up with the production rate of protein sequences, while computational techniques for protein structure predictions have matured to such a level to provide reliable structural characterization of proteins at large scale. Integration of multiple computational tools for protein structure prediction can complement experimental techniques. RESULTS: We present an automated pipeline for protein structure prediction. The centerpiece of the pipeline is our threading-based protein structure prediction system PROSPECT. The pipeline consists of a dozen tools for identification of protein domains and signal peptide, protein triage to determine the protein type (membrane or globular), protein fold recognition, generation of atomic structural models, prediction result validation, etc. Different processing and prediction branches are determined automatically by a prediction pipeline manager based on identified characteristics of the protein. The pipeline has been implemented to run in a heterogeneous computational environment as a client/server system with a web interface. Genome-scale applications on Caenorhabditis elegans, Pyrococcus furiosus and three cyanobacterial genomes are presented. AVAILABILITY: The pipeline is available at http://compbio.ornl.gov/proteinpipeline/

MOTIVATION: DNA microarray is a powerful high-throughput tool for studying gene function and regulatory networks. Due to the problem of potential cross hybridization, using full-length genes for microarray construction is not appropriate in some situations. A bioinformatic tool, PRIMEGENS, has recently been developed for the automatic design of PCR primers using DNA fragments that are specific to individual open reading frames (ORFs). RESULTS: PRIMEGENS first carries out a BLAST search for each target ORF against all other ORFs of the genome to quickly identify possible homologous sequences. Then it performs optimal sequence alignment between the target ORF and each of its homologous ORFs using dynamic programming. PRIMEGENS uses the sequence alignments to select gene- specific fragments, and then feeds the fragments to the Primer3 program to design primer pairs for PCR amplification. PRIMEGENS can be run from the command line on Unix/Linux platforms as a stand-alone package or it can be used from a Web interface. The program runs efficiently, and it takes a few seconds per sequence on a typical workstation. PCR primers specific to individual ORFs from Shewanella oneidensis MR-1 and Deinococcus radiodurans R1 have been designed. The PCR amplification results indicate that this method is very efficient and reliable for designing specific probes for microarray analysis.

MOTIVATION: Gene expression data clustering provides a powerful tool for studying functional relationships of genes in a biological process. Identifying correlated expression patterns of genes represents the basic challenge in this clustering problem. RESULTS: This paper describes a new framework for representing a set of multi-dimensional gene expression data as a Minimum Spanning Tree (MST), a concept from the graph theory. A key property of this representation is that each cluster of the expression data corresponds to one subtree of the MST, which rigorously converts a multi-dimensional clustering problem to a tree partitioning problem. We have demonstrated that though the inter-data relationship is greatly simplified in the MST representation, no essential information is lost for the purpose of clustering. Two key advantages in representing a set of multi-dimensional data as an MST are: (1) the simple structure of a tree facilitates efficient implementations of rigorous clustering algorithms, which otherwise are highly computationally challenging; and (2) as an MST-based clustering does not depend on detailed geometric shape of a cluster, it can overcome many of the problems faced by classical clustering algorithms. Based on the MST representation, we have developed a number of rigorous and efficient clustering algorithms, including two with guaranteed global optimality. We have implemented these algorithms as a computer software EXpression data Clustering Analysis and VisualizATiOn Resource (EXCAVATOR). To demonstrate its effectiveness, we have tested it on three data sets, i.e. expression data from yeast Saccharomyces cerevisiae, expression data in response of human fibroblasts to serum, and Arabidopsis expression data in response to chitin elicitation. The test results are highly encouraging. AVAILABILITY: EXCAVATOR is available on request from the authors.

It is well known that the NMR method for protein structure determination applies to small proteins and that its effectiveness decreases very rapidly as the molecular weight increases beyond about 30 kD. We have recently developed a method for protein structure determination that can fully utilize partial NMR data as calculation constraints. The core of the method is a threading algorithm that guarantees to find a globally optimal alignment between a query sequence and a template structure, under distance constraints specified by NMR/NOE data. Our preliminary tests have demonstrated that a small number of NMR/NOE distance restraints can significantly improve threading performance in both fold recognition and threading-alignment accuracy, and can possibly extend threading's scope of applicability from structural homologs to structural analogs. An accurate backbone structure generated by NMR-constrained threading can then provide a significant amount of structural information, equivalent to that provided by the NMR method with many NMR/NOE restraints; and hence can greatly reduce the amount of NMR data typically required for accurate structure determination. Our prelimenary study suggest that a small number of NOE restraints may suffice to determine adequately the all-atom structure when those restraints are incorporated in a procedure combining threading, modeling of loops and sidechains, and molecular dynamics simulation. Potentially, this new technique can expand NMR's capability to larger proteins.

MOTIVATION: This paper investigates the sequence-structure specificity of a representative knowledge based energy function by applying it to threading at the level of secondary structures of proteins. Assessing the strengths and weaknesses of an energy function at this fundamental level provides more detailed and insightful information than at the tertiary structure level and the results obtained can be useful in tertiary level threading. RESULTS: We threaded each of the 293 non-redundant proteins onto the secondary structures contained in its respective native protein (host template). We also used 68 pairs of proteins with similar folds and low sequence identity. For each pair, we threaded the sequence of one protein onto the secondary structures of the other protein. The discerning power of the total energy function and its one-body, pairwise, and mutation components is studied. We then applied our energy function to a recent study which demonstrated how a designed 11-amino acid sequence can replace distinct segments (one segment is an alpha-helix, the other is a beta-sheet) of a protein without changing its fold. We conducted random mutations of the designed sequence to determine the patterns for favorable mutations. We also studied the sequence-structure specificity at the boundaries of a secondary structure. Finally, we demonstrated how to speed up tertiary level threading by filtering out alignments found to be energetically unfavorable during the secondary structure threading. AVAILABILITY: The program is available on request from the authors. CONTACT: [email protected]

MOTIVATION: Automatic decomposition of a multi-domain protein into individual domains represents a highly interesting and unsolved problem. As the number of protein structures in PDB is growing at an exponential rate, there is clearly a need for more reliable and efficient methods for protein domain decomposition simply to keep the domain databases up-to-date. RESULTS: We present a new algorithm for solving the domain decomposition problem, using a graph-theoretic approach. We have formulated the problem as a network flow problem, in which each residue of a protein is represented as a node of the network and each residue--residue contact is represented as an edge with a particular capacity, depending on the type of the contact. A two-domain decomposition problem is solved by finding a bottleneck (or a minimum cut) of the network, which minimizes the total cross-edge capacity, using the classical Ford--Fulkerson algorithm. A multi-domain decomposition problem is solved through repeatedly solving a series of two-domain problems. The algorithm has been implemented as a computer program, called DomainParser. We have tested the program on a commonly used test set consisting of 55 proteins. The decomposition results are 78.2% in agreement with the literature on both the number of decomposed domains and the assignments of residues to each domain, which compares favorably to existing programs. On the subset of two-domain proteins (20 in number), the program assigned 96.7% of the residues correctly when we require that the number of decomposed domains is two.

Computational recognition of native-like folds from a protein fold database is considered to be a promising alternative approach to the ab initio fold prediction.We present a new and egective method forprotein fold recognition through optimally aligning (threading) an amino acid sequence and a protein fold (template).A protein fold, in our database, is represented as a se953 of core secondary structures, and the alignment quality is cletermined by three factors.They are (I) the fitness between each amino acid and the environment of its assigned (aligned) template position; (2) pairwise interaction preferences between amino acids that are spatially close,-and (3) alignment gap penalties.Our threading algorithm cons&ucts an optimum alignment between an amino acid sequence of size n and a protein fold template of size m in O((m-l-n1+o-5cMlog(n))nc+1) time and O(nm+nc+2) space, where M is the number of core secondary structures in the fold, and C is a (small) nonnegative integer, determined by a mathematical property of the pairwise interactions in the fold.C is less than or equal to 4 for about 75% of the 296 unique folds in our .database,when pairwise interactions are restricted to amino acids 5 7A apart (measured between their beta carbon atoms).An approximation scheme is developed for fold templates with C > 4, when threading requires too much memo y and time to be practical on a typical workstation.Permission to make digitalibrud copies of all or pat ofthis material for personal orclassroomuseisgranteduithoutfeeprovidedthatthecopies are not made or diiuted for profit or commercial advantage, the wpy-riShtnotice,thetitleofthepublicationanditsdateappear, andnoticek giventhatcopylightkbype -on ofthe AChL Inc To copy othenvise, to republish, to post on servers or to rediiiuteto lists, requires specific pamission ardor fee.

This paper presents an algorithm for constructing multiple gene models on a set of contigs of a large genomic clone.The algorithm first uses pattern recognition-based methods to locute ex0n.s or partial exons in each contig, and then applies protein homology or EST information from the databases, as rejerence models, to parse the predicted exons into genr models.In the phase of gene model construction, the algorithm uses a unified framework for genes ranging from situation with homologous proteins/EST3 to no homologous pvotein/EST in the database.By exploiting protein homol-0.~1~or EST information, the algorithm is able to (1) parse exons into multiple gene models over a set of DNA contigs (possibly unoriented and unordered); (2) remove falsely predicted exons; and (3) identify and locate exons missed by the initial exon prediction.

This paper presents an algorithm for constructing an optimal alignment between a three-dimensional protein structure template and an amino acid sequence. A protein structure template is given as a sequence of amino acid residue positions in three-dimensional space, along with an array of physical properties attached to each position; these residue positions are sequentially grouped into a series of core secondary structures (central helices and beta sheets). In addition to match scores and gap penalties, as in a traditional sequence-sequence alignment problem, the quality of a structure-sequence alignment is also determined by interaction preferences among amino acids aligned with structure positions that are spatially close (we call these 'long-range interactions'). Although it is known that constructing such a structure-sequence alignment in the most general form is NP-hard, our algorithm runs in polynomial time when restricted to structures with a 'modest' number of long-range amino acid interactions. In the current work, long-range interactions are limited to interactions between amino acids from different core secondary structures. Dividing the series of core secondary structures into two subseries creates a cut set of long-range interactions. If we use N, M and C to represent the size of an amino acid sequence, the size of a structure template, and the maximum cut size of long-range interactions, respectively, the algorithm finds an optimal structure-sequence alignment in O(21C NM) time, a polynomial function of N and M when C = O(log(N + M)). When running on structure-sequence alignment problems without long-range intersections, i.e. C = 0, the algorithm achieves the same asymptotic computational complexity of the Smith-Waterman sequence-sequence alignment algorithm.

Identifying genes within large regions of uncharacterized DNA is a difficult undertaking and is currently the focus of many research efforts. We describe a gene localization and modeling system, called GRAIL. GRAIL is a multiple sensor-neural network-based system. It localizes genes in anonymous DNA sequence by recognizing features related to protein-coding regions and the boundaries of coding regions, and then combines the recognized features using a neural network system. Localized coding regions are then "optimally" parsed into a gene model. Through years of extensive testing GRAIL consistently achieves about 90% of coding portions of test genes with a false positive rate of about 10% A number of genes for major genetic diseases have been located through the use of GRAIL, and over 1000 research laboratories worldwide use GRAIL on regular bases for localization of genes on their newly sequenced DNA.

This paper presents an algorithm for detecting and 'correcting' sequencing errors that occur in DNA coding regions. The types of sequencing errors addressed are insertions and deletions (indels) of DNA bases. The goal is to provide a capability which makes single-pass or low-redundancy sequence data more informative, reducing the need for high-redundancy sequencing for gene identification and characterization purposes. This would permit improved sequencing efficiency and reduce genome sequencing costs. The algorithm detects sequencing errors by discovering changes in the statistically preferred reading frame within a putative coding region and then inserts a number of 'neutral' bases at a perceived reading frame transition point to make the putative exon candidate frame consistent. We have implemented the algorithm as a front-end subsystem of the GRAIL DNA sequence analysis system to construct a version which is very error tolerant and also intend to use this as a testbed for further development of sequencing error-correction technology. Preliminary test results have shown the usefulness of this algorithm and also exhibited some of its weakness, providing possible directions for further improvement. On a test set consisting of 68 human DNA sequences with 1% randomly generated indels in coding regions, the algorithm detected and corrected 76% of the indels. The average distance between the position of an indel and the predicted one was 9.4 bases. With this subsystem in place, GRAIL correctly predicted 89% of the coding messages with 10% false message on the 'corrected' sequences, compared to 69% correctly predicted coding messages and 11% falsely predicted messages on the 'corrupted' sequences using standard GRAIL II method (version 1.2).(ABSTRACT TRUNCATED AT 250 WORDS)

This paper presents a computationally efficient algorithm, the Gene Assembly Program III (GAP III), for constructing gene models from a set of accurately-predicted 'exons'. The input to the algorithm is a set of clusters of exon candidates, generated by a new version of the GRAIL coding region recognition system. The exon candidates of a cluster differ in their presumed edges and occasionally in their reading frames. Each exon candidate has a numerical score representing its 'probability' of being an actual exon. GAP III uses a dynamic programming algorithm to construct a gene model, complete or partial, by optimizing a predefined objective function. The optimal gene models constructed by GAP III correspond very well with the structures of genes which have been determined experimentally and reported in the Genome Sequence Database (GSDB). On a test set of 137 human and mouse DNA sequences consisting of 954 true exons, GAP III constructed 137 gene models using 892 exons, among which 859 (859/954 = 90%) are true exons and 33 (33/892 = 3%) are false positive. Among the 859 true positives, 635 (74%) match the actual exons exactly, and 838 (98%) have at least one edge correct. GAP III is computationally efficient. If we use E and C to represent the total number of exon candidates in all clusters and the number of clusters, respectively, the running time of GAP III is proportional to (E x C).

Efficient algorithms are presented for the matroid intersection problem and generalizations. The algorithm for weighted intersection works by scaling the weights. The cardinality algorithm is a special case that takes advantage of greater structure. Efficiency of the algorithms is illustrated by several implementations. On graphic matroids the algorithms run close to the best bounds for trivial matroids (i.e. ordinary bipartite graph matching): O( square root nm log n) for cardinality intersection and O( square root nm log/sup 2/n log(nN)) for weighted intersection (n, m, and N denote the number of vertices, edges, and largest edge weight, respectively; weights are assumed integral). Efficient algorithms are also given for linear matroids. These include both algorithms that are practical and algorithms exploiting fast matrix multiplication.>