BACKGROUND
expressed sequence tags  are partial sequences of cdna sequences that represent expressed dna sequences .
these short fragments are usually generated by sequencing a few hundred nucleotides from either the 5' end  or the 3' end  of a cdna sequence.
libraries of ests can be generated relatively fast and are inexpensive.
therefore, they often serve as a gene discovery tool.
est libraries are often used to detect genes that are linked with certain diseases or genes specifically expressed in certain tissues.
for example, vasmatzis et al.
<cit>  clustered ests using a rudimentary sequence identity metric to discover new genes specific to the human prostate.
more recently, bera et al.
<cit>  used a similar procedure to identify mrp <dig> and mrp <dig>  genes highly expressed in breast cancer.
est libraries were also used to predict, for example, secreted proteins  <cit> .
while est libraries are potentially very informative, they are difficult to process and analyze.
since ests are sequenced by scanning the cdna only once, they have relatively high error rates due to either sequencing errors  or frameshift errors.
thus, nucleic acid sequence databases are flooded with short, redundant and inaccurate or contaminated sequences.
moreover, ests are rarely annotated and the gene protein product is usually undefined.
since ests are usually either too short or too noisy for sequence alignment methods to be effective, mapping est sequences to protein products can be a difficult task without some pre-processing.
the signal is often too weak, or the est might be outside of the translated region.
alternatively, the protein product might not exist in protein sequence databases.
this poses a major problem for experimental molecular biologists who generate large est libraries to study specific biological systems.
a careful investigation of genes is time consuming, therefore only a few of the many est sequences are usually selected for detailed study.
to maximize efficiency, the sequences that are selected are usually ests that can be mapped to well-studied genes.
with the vast majority of the original est data ignored, potential advances and new discoveries are limited.
these problems can have a major impact on high-throughput studies.
for example, microarrays are commonly used to study a wide variety of biological questions and the ability to correlate differentially expressed genes with a particular experimental manipulation can provide new insight into a given biological problem.
however, ests with no known function comprise 40–60% of the genes in the genome and therefore many of these differentially expressed genes are likely to be ests.
without any further insight into their function, the role of these ests in a given biological problem cannot be inferred.
instead, much of the emphasis in analyzing microarray data is devoted to grouping together genes with known function into various categories .
as a result, most microarray experiments essentially act to associate known genes with new biological paradigms, and ignore much of the data.
indeed, in recognition of this fact, affymetrix genechip arrays can be ordered that only contain genes of known function, and do not contain ests that cannot be annotated.
similar problems characterize proteomic screens, and the analysis of proteins that are induced or repressed under specific experimental conditions typically focuses only on those with known function.
in still another example, genetic screens for mutants will often identify genes that previously had no known function.
while these ests can now be functionally defined by their observed phenotype, detecting similarity to other proteins with known function can affect the interpretation of the phenotype as well as shape the design of future experiments.
in view of these examples, a tool that can associate ests with genes of known function would be of great value to biologists looking to understand a given experimental problem.
related studies
to increase the effectiveness of est sequences, one can use clustering procedures.
these procedures build upon the high redundancy in est libraries.
the clusters often resolve sequencing errors and are easier to map to protein products than individual ests.
three popular databases of est clusters are unigene  <cit> , tigr  <cit>  and stack  <cit> .
other studies developed models for direct gene prediction from est data.
estscan  <cit>  is a program for detecting potential coding regions in est sequences that is based on a hidden markov model.
given a nucleic acid sequence, estscan uses the viterbi decoding algorithm to determine the most probable path through the model and to infer the most likely coding region or identify multiple coding regions.
the authors report 95% detection rate of true coding regions at about 18% rate of false positives.
diana-est  <cit>  is a program that analyzes ests to determine coding regions and frame-shift errors using three different neural networks .
the authors report accuracy of about 90% at the nucleotide level.
while these methods can be useful for the prediction of coding regions, they do not attempt to map the predicted genes to their protein products.
that usually entails additional analysis, blast searches and post processing of the search results.
pipeonline  <cit>  was developed in response to the need for large-scale est analysis.
users upload raw sequence data which is first cleaned and assembled into a non-redundant set of contigs.
pipeonline then uses blast to find protein sequences which are similar to the contigs.
estannotator  <cit>  is another high-throughput est analysis utility which uses a series of blast searches to cluster, assemble, and annotate ests.
the utility first attempts to annotate the input sequences by querying them against multiple nucleotide databases.
if this first step is unsuccessful, estannotator clusters and assembles the ests by iterating applications of blast and cap  <cit>  and the resulting contigs are queried against nucleotide and protein databases.
a similar approach is employed in prot4est  <cit>  which links together several est prediction algorithms.
it feeds the input sequences through a pipeline of sequence comparisons against various databases starting with rrna databases  followed by mitochondrial protein databases  and other protein databases.
if all these comparisons fail to produce significant matches, prot4est uses estscan or decoder to annotate the sequence.
another est analysis package is partigene  <cit>  which predicts possible protein products through clustering, sequence comparison and application of other prediction algorithms such as prot4est, decoder, and estscan.
also relevant is estima  <cit>  which is an application designed to assist with est data management and annotation.
the estima web interface allows users to query their est data.
users can, for example, find all ests associated with a particular go term, run blast queries against the sequences in the database, view contigs and chromatograms, and view blast derived annotation.
current work is largely concerned with identifying gene structure and alternative splicing variants.
for example, the latest version of geneseqer  <cit>  predicts gene structure  of a genomic dna sequence by aligning cdna and est sequences to the long dna sequence and using splice site prediction methods.
in addition to these programs there are many other gene prediction programs that are not necessarily geared for est data and are usually applied to longer nucleic acid sequences or complete genomes .
as the discussion above suggests, analysis of est data is not a simple task.
most est analysis tools involve a lot of data processing that cannot be done in real time and some require the user to have all the requisite software locally available.
this limits the usability of these tools.
in this paper we describe a system that utilizes the biozon infrastructure  <cit>  and uses est cluster data together with other data sets, such as established relations between dna and proteins and similarity data between proteins, to map ests to their protein products.
our method is very fast; it uses pre-computed data and does not require intense computations at the query stage.
the system can also identify the ests whose protein products have specific functions .
in the next sections we describe the main elements of the biozon's est2prot mapping tool and demonstrate its utility in predicting est sequences whose likely protein products are involved in nerve regeneration.
implementation
biozon's est2prot system builds upon the infrastructure of biozon.
it uses multiple data sets, all integrated into a single, tightly connected schema that enables great flexibility in querying for complex relations between entities.
specifically, we utilize the many paths that exist between entities in the biozon data graph to map ests to protein products.
biozon
the biozon database  <cit>  is a system that unifies multiple biological databases consisting of a variety of heterogeneous data types  into a single schema.
logically, the database is viewed as a large graph where biological entities correspond to nodes and edges correspond to relations, as is depicted schematically in figure  <dig>  the underlying assumption of biozon is that any biological entity or process can be associated with a physical object or a set of physical objects.
therefore, physical objects form the backbone of the database and their physical properties serve as the actual identifiers.
for example, a protein is uniquely identified by its amino acid sequence and a dna by its sequence of nucleotides.
an interaction between two proteins or between a protein and a dna is represented as a set of physical objects , a protein family is a set of protein sequences, a metabolic pathway is a set of reactions  family) and so on.
each type of object is also associated with an identity operator that is used to compare entities and determine whether they are identical .
the reliance on physical entities and sets of physical entities as our backbone is especially useful for data integration since it allows unambiguous unification of many entities from different databases based on their physical properties.
for example, a protein sequence that exists in swiss-prot  <cit> , pir  <cit>  and refseq  <cit>  will be mapped to the same sequence object  in the data graph and the information that is available in these sources about this protein will be accessible from a single entry point in biozon.
unlike identifiers such as accession numbers and cross-references that are potentially unstable or inconsistent , relationships that are established based on physical non-redundant biozon objects are highly reliable and are materialized explicitly in the data graph.
this has a great benefit in linking entities from disparate sources.
for example, paths are formed between protein domains from interpro  <cit>  and interactions from bind  <cit>  or between protein structures from pdb  <cit>  and metabolic pathways from kegg  <cit> .
relations between objects in biozon can have different meanings, depending on the entities they connect.
for example, 'member of' is a relation that connects a protein to a protein family or an est to a est cluster.
the relation 'manifests' relates a protein sequence to its structure, 'encodes' relates a dna sequence to protein sequence, 'similar' relates two similar protein sequences and so on.
the large-scale data integration results in a highly connected graph structure that allows one to see each entity in its broader context with all its related entities; a context that cannot be determined from any one source.
utilizing its graph structure, biozon allows complex and fuzzy searches on the data graph that span multiple data types and specify desired interrelationships between them.
for more details on the biozon schema and its various components see  <cit> .
mapping ests to proteins
the est2prot system exploits a subset of the biozon schema, including dna sequences, proteins and est clusters and the 'encodes', 'substring' and 'similar' relations.
we explore five different direct paths in the biozon data graph, and say that est s is directly mapped to protein p if:
<dig>  s encodes p
<dig>  s is a substring of dna s' near an encoding region of s' which encodes for p .
<dig>  s is a member of a unigene cluster to which ncbi assigns p
<dig>  s is a member of a unigene cluster containing s' and s' encodes p
<dig>  s is a member of a unigene cluster containing s' and s' is a substring of s" near an encoding region of s" which encodes for p
we say an est s maps to protein p if s directly maps to p or if s directly maps to p' and p' is similar to p as described in section 'relations'.
an overview of our system is given in figure  <dig>
it should be noted that while unigene relies just on blast searches with respect to eight model organisms, biozon uses all these paths at once to create a more comprehensive mapping between ests and proteins.
it is the tightly connected schema of biozon that enables immediate information flow and deduction of paths between entities, without having to resort to external resources outside the database or expensive computations.
most notably, the materialization of similarity data brings forward instantly an unprecedented amount of information that otherwise would requite millions of blast searches.
this is especially important since often proteins with unknown properties can be characterized based on their similarity with better studied homologous proteins.
data sets
dna sequences are gleaned from genbank records.
as of september  <dig> , biozon contains  <dig> , <dig> unique dna sequences.
proteins are extracted from several databases  and unified into a non-redundant set based on their physical sequence of amino acids .
all together, biozon contains  <dig> , <dig> unique protein sequences in release  <dig> .
est clusters
in response to the growing chaos of est data, ncbi developed unigene  <cit> , a gene-oriented clustering of transcribed nucleic acid sequences.
unigene includes only protein-coding genes which have at least  <dig> high quality non-repetitive base pairs.
it also requires that its clusters be 3' anchored.
clusters not showing evidence of reaching the 3' terminus are eliminated .
each unigene cluster represents a gene and its alternative splice forms.
associated with each cluster are the gene's possible protein products.
these proteins are chosen by comparing the cluster sequences with the available proteomes of eight model organisms .
for each model organism, the cluster is assigned the protein most similar to a representative sequence with respect to some similarity threshold .
if no sequence in a cluster has a significant blast match, then that cluster is left unassigned.
in fact, unigene do not assign proteins to 42% of its clusters.
unigene clusters for  <dig> organisms were integrated into the biozon schema and in release  <dig>  this dataset contains  <dig>  clusters with a total of  <dig> , <dig> est sequences.
relations
to determine possible links between est sequences and proteins we explore several paths, as is depicted in figure  <dig>  these paths are based on the following relations.
the 'encodes' relation
this relation ties nucleic acid sequences and proteins.
the relations are not established based on cross links, but rather based on physical properties.
each encodes relation  indicates that the dna sequence d contains a coding region that can be translated completely to the protein sequence p.
the 'unigene encodes' relation
this relation is established between unigene clusters and proteins.
the relations are established by the unigene team as described above.
the 'substring' relation
this relation exists between strings of the same data type .
a substring relation  indicates that the dna sequence d is a fragment of the longer dna sequence d'.
of special interest are substring relations that place a fragment d near a coding region of d'.
if d is no more than  <dig> base pairs away from overlapping a coding region of d' that encodes for protein p, then we say that d is linked to p .
the 'similarity' relation
the similarity relation is one of the most fundamental relations in biology, frequently used for functional inference.
biozon computes and stores similarity relationships between proteins based on sequence, structure or expression profiles.
the integration of similarity data enables the propagation of information from well-studied entries to uncharacterized ones.
biozon contains pairwise similarities for about  <dig> , <dig> sequences, which were computed using blast  <cit> , resulting in a total of about  <dig>  billion significant pairwise similarities .
these similarity relations are used to extend the mappings from ests to proteins, thus increasing the set of functional descriptors that can be associated with an est.
the great advantage of the similarity relations of biozon is the scalability and accessibility.
since est analysis requires expensive database searches to search for possible protein products, it is difficult to scale existing methods for est analysis to large libraries.
by materializing similarity data, knowledge propagation in biozon becomes immediate, thus facilitating the task of function assignment.
target proteins
a biologist might be interested only in ests that are linked to a specific biological system.
to address this need, the est2prot system can be queried with respect to specific biological descriptors.
the system collects a set of target proteins with relevant functions and reports the ests which map to at least one target protein.
we define our target proteins by target descriptors, which are based on go terms  <cit>  and swissprot keywords  <cit> .
swissprot keywords are descriptors that are associated with proteins based on manual curation.
these keywords have been used in many studies to automatically annotate proteins or assess the biological function of protein clusters .
the gene ontology  functional descriptors are obtained from the go database  <cit> .
go terms are organized in an acyclic tree-like graph where a node's parent represents a property that is more general than the node's property.
however, unlike a tree form of a graph, in the go graph it is possible to have more than one path leading from the root to a node.
also, a protein may be assigned more than one go term, each one on a different branch of the graph .
go terms in biozon were collected from multiple sources, downloaded from the go consortium website and extracted from databases such as uniprot.
a total of  <dig> , <dig> proteins in biozon can be associated with go terms in release  <dig> .
.
user interface
given an est  est2prot explores all possible paths leading from that sequence to protein products in the biozon data graph.
the user is presented with multiple pages that summarize the information and rank the proteins based on our confidence in the association .
the first page provides the entry point to the biozon data graph for the query est and each page is linked to other pages with increasingly detailed information on the mapped proteins.
for more information on the webserver see the appendix .
RESULTS
statistics
we analyzed in detail  <dig>  unigene clusters of mouse and human that were available as of april  <dig> .
these clusters contain a total of  <dig> , <dig> nucleic acid sequences, of which  <dig>  are encoding sequences .
these encoding ests can be mapped directly to proteins using type i paths in biozon.
a total of  <dig>  unigene clusters contain at least one encoding dna sequence.
of the  <dig>  unigene clusters,  <dig>  are associated with proteins by the unigene team .
these clusters account for  <dig> , <dig> of the  <dig> , <dig> est sequences .
by considering also direct relationships that are formed by coding sequences , biozon maps  <dig>  clusters to proteins.
including also type  <dig> paths  results in  <dig>  mapped clusters.
it should be noted that the contributions of the biozon-based paths of type  <dig> and  <dig> are substantial in and of themselves.
for example,  <dig>  clusters can be mapped based on class  <dig> paths alone and  <dig>  clusters can be mapped based on type  <dig> paths alone.
the latter is the result of  <dig>  substring relations that we detected in the mouse genome .
these substring-superstring relations establish  <dig>  relations between ests and proteins.
the additional paths that biozon explores naturally increase the number of ests that can be mapped to proteins.
moreover, these mappings are of high quality as they do not rely on cross-links by identifiers but rather on computationally validated transformations and relations.
the most substantial difference between unigene and the est2prot system lies in the number of paths formed and the number of proteins that can be mapped to est clusters.
when using only unigene, there are  <dig>  relations between unigene clusters and protein sequences.
with biozon, the number of relations increases by 36% to  <dig>   thus enriching the protein information significantly.
interestingly, the  <dig>  proteins that are mapped to  <dig>  clusters by unigene  are reduced to only  <dig>  unique protein sequences .
moreover,  <dig>  proteins are mapped to at least two clusters.
the most extreme case is of pir protein s <dig>  with biozon docid  <dig> .
that is mapped to no less than  <dig> clusters.
similarly, genpept protein gi: <dig>  is mapped to  <dig> unigene clusters.
these numbers suggest very high redundancy and overlap between unigene clusters, which is surprising given that clusters are expected to correlate with different genes.
since biozon adopts the unigene clusters as is, the redundancy is also inherent to our mappings.
however, the redundancy level is much lower and the  <dig>  proteins that are mapped using paths of type  <dig>   <dig> and  <dig> are reduced to  <dig>  unique proteins .
it should be noted that in some cases unigene clusters "physically" overlap, as is the case for unigene clusters mm.
<dig> and mm.
<dig>  a total of  <dig> human clusters overlap with other human clusters, and  <dig> mouse clusters overlap with other mouse clusters.
this can happen when multiple ests with different accession numbers are actually identical.
since biozon employs a non-redundant object model, these identical sequences are mapped to the same nucleic acid sequence object in biozon.
it is unclear why these ests are clustered in unigene to different clusters, whether the ests have different locations , and if the unigene clustering algorithm considers the location when grouping ests into clusters.
examples
as part of a study of pathways in the mouse olfactory system we were interested in identifying mouse ests whose protein products have brain-related functions from approximately  <dig>  mouse ests provided by nia and bmap  <cit> .
as target keywords and go terms we chose those containing the text "brain," "nerv," or "neuro" anywhere in the keyword's or go term's description.
we also eliminate by hand keywords describing irrelevant diseases.
our target proteins are simply those described by the target keywords and go terms .
of the  <dig>  sequences in bmap,  <dig>  can be mapped to  <dig>  proteins using unigene alone.
with the est2prot system, biozon maps  <dig>  ests to  <dig>  proteins .
as many as  <dig>  ests  can be mapped to target proteins.
when similarity data is considered the number of ests that can be mapped to target proteins more than doubles to  <dig>  .
to demonstrate the utility of the biozon est analysis tool, we used it to determine the potential function of ests identified in a microarray-based screen.
this screen was designed to identify genes involved in axon pathfinding and target recognition in the mouse olfactory system.
in our preliminary studies we identified thirteen genes that could potentially play key roles in this process.
however, eight of these were ests with no known function or annotation.
biozon was able to find matches for four of the eight ests.
interestingly, one est  that is classified to a unigene cluster of unknown function  was predicted in biozon to have similarity to protocadherins.
protocadherins are members of the cadherin superfamily, and are thought to play key roles in axon guidance, target recognition, and synaptogenesis  <cit> .
our preliminary results suggest that this est is indeed a member of the cadherin superfamily, and may therefore be involved in mediating target recognition within the olfactory system.
without such annotation, this est would likely have been ignored, and a valuable potential guidance cue may not have been recognized.
other ests  that belong to the same unigene cluster as ai <dig> are also linked with protocadherins in biozon, through similar paths, although neither unigene nor entrez suggest such links.
CONCLUSIONS
to allow biologists to exploit est libraries more efficiently and focus their search more effectively we developed an est mapping system that identifies for each est its most likely protein products.
our analysis relies heavily on ncbi's unigene clustering, biozon's infrastructure and the massive protein similarity data contained within.
our tool can help experimental biologists filter a large collection of nucleic acid sequences and predict which sequences are germane to a given biological system.
as an extensive and established est analysis tool, unigene is our main source of information.
biozon augments this data with other datasets that are extracted from multiple databases.
for example, unigene uses only  <dig> model organisms to map est clusters to proteins, while biozon uses protein sequences from thousands of fully or partly sequenced genomes, in addition to a myriad of other biological information on relationships between biological entities to establish multiple paths between est sequences and protein sequences.
biozon also analyzes sequences in the ncbi est database  that are excluded from the gene-oriented unigene, such as rrna and mitochondiral sequences.
the retrieval of this information is done in real-time by traversing paths in the data graph.
this is made possible because of the graph-schema of biozon that was designed to handle large-scale integration of dynamically changing biological data, where all datasets are compiled into a single tightly-connected graph.
since the data in biozon relies on physical properties  rather than just database cross links, the graph-link structure is of high quality.
moreover, the biozon database was designed to sustain frequent updates of its sources, and as such it ensures that the mapping utilizes newly sequenced dna and protein sequences.
biozon also strives for completeness, and the similarity data makes up for missing and inconsistent data.
this has a major impact for example, when compiling the functional descriptors from the go database.
since go data is partial, and since it is derived from multiple sources, it is not necessarily coherent.
consequently, in many cases proteins that are very similar based on sequence are not necessarily associated with the same set of go terms, and this can greatly reduce the effectiveness of the mapping.
by incorporating similarity relations biozon extends and enrich the set of functional descriptors that can be associated with a given est.
the est2prot system can be accessed from the biozon webserver.
information on the web tools is available in the appendix .
availability and requirements
est2prot is available online at .
any user can upload and analyze her or his est data through any javascript-enabled web browser such as netscape, mozzila or explorer, and obtain the mapping in real-time.
authors' contributions
ps implemented the est2prot system and ran experiments over the mouse and human genomes.
gy and dl conceived of the study.
gy designed the system.
dl participated in the analysis of the results.
all authors contributed, read and approved the final manuscript.
supplementary material
additional file 1
appendix the est2prot webserver.
the appendix takes the reader through the main web pages that make-up the est2prot webserver, with explanations of the output format of each page and snapshots that exemplify the type of information provided.
click here for file
acknowledgements
we thank aaron birkland for his help with the biozon database.
this work is supported by the national science foundation under grant no.
<dig> as part of the nsf/nih collaborative research in computational neuroscience program and by sun microsystems.
figures and tables

 expressed sequence tags are partial sequences of cdna sequences that represent expressed dna sequences. these short fragments are usually generated by sequencing a few hundred nucleotides from either the 5' end or the 3' end of a cdna sequence. libraries of ests can be generated relatively fast and are inexpensive. therefore, they often serve as a gene discovery tool. est libraries are often used to detect genes that are linked with certain diseases or genes specifically expressed in certain tissues. for example, vasmatzis et al. clustered ests using a rudimentary sequence identity metric to discover new genes specific to the human prostate. more recently, bera et al. used a similar procedure to identify mrp and mrp genes highly expressed in breast cancer. est libraries were also used to predict, for example, secreted proteins. while est libraries are potentially very informative, they are difficult to process and analyze. since ests are sequenced by scanning the cdna only once, they have relatively high error rates due to either sequencing errors or frameshift errors. thus, nucleic acid sequence databases are flooded with short, redundant and inaccurate or contaminated sequences. moreover, ests are rarely annotated and the gene protein product is usually undefined. since ests are usually either too short or too noisy for sequence alignment methods to be effective, mapping est sequences to protein products can be a difficult task without some pre-processing. the signal is often too weak, or the est might be outside of the translated region. alternatively, the protein product might not exist in protein sequence databases. this poses a major problem for experimental molecular biologists who generate large est libraries to study specific biological systems. a careful investigation of genes is time consuming, therefore only a few of the many est sequences are usually selected for detailed study. to maximize efficiency, the sequences that are selected are usually ests that can be mapped to well-studied genes. with the vast majority of the original est data ignored, potential advances and new discoveries are limited. these problems can have a major impact on high-throughput studies. for example, microarrays are commonly used to study a wide variety of biological questions and the ability to correlate differentially expressed genes with a particular experimental manipulation can provide new insight into a given biological problem. however, ests with no known function comprise 40–60% of the genes in the genome and therefore many of these differentially expressed genes are likely to be ests. without any further insight into their function, the role of these ests in a given biological problem cannot be inferred. instead, much of the emphasis in analyzing microarray data is devoted to grouping together genes with known function into various categories. as a result, most microarray experiments essentially act to associate known genes with new biological paradigms, and ignore much of the data. indeed, in recognition of this fact, affymetrix genechip arrays can be ordered that only contain genes of known function, and do not contain ests that cannot be annotated. similar problems characterize proteomic screens, and the analysis of proteins that are induced or repressed under specific experimental conditions typically focuses only on those with known function. in still another example, genetic screens for mutants will often identify genes that previously had no known function. while these ests can now be functionally defined by their observed phenotype, detecting similarity to other proteins with known function can affect the interpretation of the phenotype as well as shape the design of future experiments. in view of these examples, a tool that can associate ests with genes of known function would be of great value to biologists looking to understand a given experimental problem. related studies to increase the effectiveness of est sequences, one can use clustering procedures. these procedures build upon the high redundancy in est libraries. the clusters often resolve sequencing errors and are easier to map to protein products than individual ests. three popular databases of est clusters are unigene, tigr and stack. other studies developed models for direct gene prediction from est data. estscan is a program for detecting potential coding regions in est sequences that is based on a hidden markov model. given a nucleic acid sequence, estscan uses the viterbi decoding algorithm to determine the most probable path through the model and to infer the most likely coding region or identify multiple coding regions. the authors report 95% detection rate of true coding regions at about 18% rate of false positives. diana-est is a program that analyzes ests to determine coding regions and frame-shift errors using three different neural networks. the authors report accuracy of about 90% at the nucleotide level. while these methods can be useful for the prediction of coding regions, they do not attempt to map the predicted genes to their protein products. that usually entails additional analysis, blast searches and post processing of the search results. pipeonline was developed in response to the need for large-scale est analysis. users upload raw sequence data which is first cleaned and assembled into a non-redundant set of contigs. pipeonline then uses blast to find protein sequences which are similar to the contigs. estannotator is another high-throughput est analysis utility which uses a series of blast searches to cluster, assemble, and annotate ests. the utility first attempts to annotate the input sequences by querying them against multiple nucleotide databases. if this first step is unsuccessful, estannotator clusters and assembles the ests by iterating applications of blast and cap and the resulting contigs are queried against nucleotide and protein databases. a similar approach is employed in prot4est which links together several est prediction algorithms. it feeds the input sequences through a pipeline of sequence comparisons against various databases starting with rrna databases followed by mitochondrial protein databases and other protein databases. if all these comparisons fail to produce significant matches, prot4est uses estscan or decoder to annotate the sequence. another est analysis package is partigene which predicts possible protein products through clustering, sequence comparison and application of other prediction algorithms such as prot4est, decoder, and estscan. also relevant is estima which is an application designed to assist with est data management and annotation. the estima web interface allows users to query their est data. users can, for example, find all ests associated with a particular go term, run blast queries against the sequences in the database, view contigs and chromatograms, and view blast derived annotation. current work is largely concerned with identifying gene structure and alternative splicing variants. for example, the latest version of geneseqer predicts gene structure of a genomic dna sequence by aligning cdna and est sequences to the long dna sequence and using splice site prediction methods. in addition to these programs there are many other gene prediction programs that are not necessarily geared for est data and are usually applied to longer nucleic acid sequences or complete genomes. as the discussion above suggests, analysis of est data is not a simple task. most est analysis tools involve a lot of data processing that cannot be done in real time and some require the user to have all the requisite software locally available. this limits the usability of these tools. in this paper we describe a system that utilizes the biozon infrastructure and uses est cluster data together with other data sets, such as established relations between dna and proteins and similarity data between proteins, to map ests to their protein products. our method is very fast; it uses pre-computed data and does not require intense computations at the query stage. the system can also identify the ests whose protein products have specific functions. in the next sections we describe the main elements of the biozon's est2prot mapping tool and demonstrate its utility in predicting est sequences whose likely protein products are involved in nerve regeneration. implementation biozon's est2prot system builds upon the infrastructure of biozon. it uses multiple data sets, all integrated into a single, tightly connected schema that enables great flexibility in querying for complex relations between entities. specifically, we utilize the many paths that exist between entities in the biozon data graph to map ests to protein products. biozon the biozon database is a system that unifies multiple biological databases consisting of a variety of heterogeneous data types into a single schema. logically, the database is viewed as a large graph where biological entities correspond to nodes and edges correspond to relations, as is depicted schematically in figure the underlying assumption of biozon is that any biological entity or process can be associated with a physical object or a set of physical objects. therefore, physical objects form the backbone of the database and their physical properties serve as the actual identifiers. for example, a protein is uniquely identified by its amino acid sequence and a dna by its sequence of nucleotides. an interaction between two proteins or between a protein and a dna is represented as a set of physical objects, a protein family is a set of protein sequences, a metabolic pathway is a set of reactions family) and so on. each type of object is also associated with an identity operator that is used to compare entities and determine whether they are identical. the reliance on physical entities and sets of physical entities as our backbone is especially useful for data integration since it allows unambiguous unification of many entities from different databases based on their physical properties. for example, a protein sequence that exists in swiss-prot, pir and refseq will be mapped to the same sequence object in the data graph and the information that is available in these sources about this protein will be accessible from a single entry point in biozon. unlike identifiers such as accession numbers and cross-references that are potentially unstable or inconsistent, relationships that are established based on physical non-redundant biozon objects are highly reliable and are materialized explicitly in the data graph. this has a great benefit in linking entities from disparate sources. for example, paths are formed between protein domains from interpro and interactions from bind or between protein structures from pdb and metabolic pathways from kegg. relations between objects in biozon can have different meanings, depending on the entities they connect. for example,'member of' is a relation that connects a protein to a protein family or an est to a est cluster. the relation'manifests' relates a protein sequence to its structure,'encodes' relates a dna sequence to protein sequence,'similar' relates two similar protein sequences and so on. the large-scale data integration results in a highly connected graph structure that allows one to see each entity in its broader context with all its related entities; a context that cannot be determined from any one source. utilizing its graph structure, biozon allows complex and fuzzy searches on the data graph that span multiple data types and specify desired interrelationships between them. for more details on the biozon schema and its various components see. mapping ests to proteins the est2prot system exploits a subset of the biozon schema, including dna sequences, proteins and est clusters and the'encodes','substring' and'similar' relations. we explore five different direct paths in the biozon data graph, and say that est s is directly mapped to protein p if: s encodes p s is a substring of dna s' near an encoding region of s' which encodes for p. s is a member of a unigene cluster to which ncbi assigns p s is a member of a unigene cluster containing s' and s' encodes p s is a member of a unigene cluster containing s' and s' is a substring of s" near an encoding region of s" which encodes for p we say an est s maps to protein p if s directly maps to p or if s directly maps to p' and p' is similar to p as described in section'relations'. an overview of our system is given in figure it should be noted that while unigene relies just on blast searches with respect to eight model organisms, biozon uses all these paths at once to create a more comprehensive mapping between ests and proteins. it is the tightly connected schema of biozon that enables immediate information flow and deduction of paths between entities, without having to resort to external resources outside the database or expensive computations. most notably, the materialization of similarity data brings forward instantly an unprecedented amount of information that otherwise would requite millions of blast searches. this is especially important since often proteins with unknown properties can be characterized based on their similarity with better studied homologous proteins. data sets dna sequences are gleaned from genbank records. as of september, biozon contains, unique dna sequences. proteins are extracted from several databases and unified into a non-redundant set based on their physical sequence of amino acids. all together, biozon contains, unique protein sequences in release. est clusters in response to the growing chaos of est data, ncbi developed unigene, a gene-oriented clustering of transcribed nucleic acid sequences. unigene includes only protein-coding genes which have at least high quality non-repetitive base pairs. it also requires that its clusters be 3' anchored. clusters not showing evidence of reaching the 3' terminus are eliminated. each unigene cluster represents a gene and its alternative splice forms. associated with each cluster are the gene's possible protein products. these proteins are chosen by comparing the cluster sequences with the available proteomes of eight model organisms. for each model organism, the cluster is assigned the protein most similar to a representative sequence with respect to some similarity threshold. if no sequence in a cluster has a significant blast match, then that cluster is left unassigned. in fact, unigene do not assign proteins to 42% of its clusters. unigene clusters for organisms were integrated into the biozon schema and in release this dataset contains clusters with a total of, est sequences. relations to determine possible links between est sequences and proteins we explore several paths, as is depicted in figure these paths are based on the following relations. the'encodes' relation this relation ties nucleic acid sequences and proteins. the relations are not established based on cross links, but rather based on physical properties. each encodes relation indicates that the dna sequence d contains a coding region that can be translated completely to the protein sequence p. the'unigene encodes' relation this relation is established between unigene clusters and proteins. the relations are established by the unigene team as described above. the'substring' relation this relation exists between strings of the same data type. a substring relation indicates that the dna sequence d is a fragment of the longer dna sequence d'. of special interest are substring relations that place a fragment d near a coding region of d'. if d is no more than base pairs away from overlapping a coding region of d' that encodes for protein p, then we say that d is linked to p. the'similarity' relation the similarity relation is one of the most fundamental relations in biology, frequently used for functional inference. biozon computes and stores similarity relationships between proteins based on sequence, structure or expression profiles. the integration of similarity data enables the propagation of information from well-studied entries to uncharacterized ones. biozon contains pairwise similarities for about, sequences, which were computed using blast, resulting in a total of about billion significant pairwise similarities. these similarity relations are used to extend the mappings from ests to proteins, thus increasing the set of functional descriptors that can be associated with an est. the great advantage of the similarity relations of biozon is the scalability and accessibility. since est analysis requires expensive database searches to search for possible protein products, it is difficult to scale existing methods for est analysis to large libraries. by materializing similarity data, knowledge propagation in biozon becomes immediate, thus facilitating the task of function assignment. target proteins a biologist might be interested only in ests that are linked to a specific biological system. to address this need, the est2prot system can be queried with respect to specific biological descriptors. the system collects a set of target proteins with relevant functions and reports the ests which map to at least one target protein. we define our target proteins by target descriptors, which are based on go terms and swissprot keywords. swissprot keywords are descriptors that are associated with proteins based on manual curation. these keywords have been used in many studies to automatically annotate proteins or assess the biological function of protein clusters. the gene ontology functional descriptors are obtained from the go database. go terms are organized in an acyclic tree-like graph where a node's parent represents a property that is more general than the node's property. however, unlike a tree form of a graph, in the go graph it is possible to have more than one path leading from the root to a node. also, a protein may be assigned more than one go term, each one on a different branch of the graph. go terms in biozon were collected from multiple sources, downloaded from the go consortium website and extracted from databases such as uniprot. a total of, proteins in biozon can be associated with go terms in release.. user interface given an est est2prot explores all possible paths leading from that sequence to protein products in the biozon data graph. the user is presented with multiple pages that summarize the information and rank the proteins based on our confidence in the association. the first page provides the entry point to the biozon data graph for the query est and each page is linked to other pages with increasingly detailed information on the mapped proteins. for more information on the webserver see the appendix.  statistics we analyzed in detail unigene clusters of mouse and human that were available as of april. these clusters contain a total of, nucleic acid sequences, of which are encoding sequences. these encoding ests can be mapped directly to proteins using type i paths in biozon. a total of unigene clusters contain at least one encoding dna sequence. of the unigene clusters, are associated with proteins by the unigene team. these clusters account for, of the, est sequences. by considering also direct relationships that are formed by coding sequences, biozon maps clusters to proteins. including also type paths results in mapped clusters. it should be noted that the contributions of the biozon-based paths of type and are substantial in and of themselves. for example, clusters can be mapped based on class paths alone and clusters can be mapped based on type paths alone. the latter is the result of substring relations that we detected in the mouse genome. these substring-superstring relations establish relations between ests and proteins. the additional paths that biozon explores naturally increase the number of ests that can be mapped to proteins. moreover, these mappings are of high quality as they do not rely on cross-links by identifiers but rather on computationally validated transformations and relations. the most substantial difference between unigene and the est2prot system lies in the number of paths formed and the number of proteins that can be mapped to est clusters. when using only unigene, there are relations between unigene clusters and protein sequences. with biozon, the number of relations increases by 36% to thus enriching the protein information significantly. interestingly, the proteins that are mapped to clusters by unigene are reduced to only unique protein sequences. moreover, proteins are mapped to at least two clusters. the most extreme case is of pir protein s with biozon docid. that is mapped to no less than clusters. similarly, genpept protein gi: is mapped to unigene clusters. these numbers suggest very high redundancy and overlap between unigene clusters, which is surprising given that clusters are expected to correlate with different genes. since biozon adopts the unigene clusters as is, the redundancy is also inherent to our mappings. however, the redundancy level is much lower and the proteins that are mapped using paths of type and are reduced to unique proteins. it should be noted that in some cases unigene clusters "physically" overlap, as is the case for unigene clusters mm. and mm. a total of human clusters overlap with other human clusters, and mouse clusters overlap with other mouse clusters. this can happen when multiple ests with different accession numbers are actually identical. since biozon employs a non-redundant object model, these identical sequences are mapped to the same nucleic acid sequence object in biozon. it is unclear why these ests are clustered in unigene to different clusters, whether the ests have different locations, and if the unigene clustering algorithm considers the location when grouping ests into clusters. examples as part of a study of pathways in the mouse olfactory system we were interested in identifying mouse ests whose protein products have brain-related functions from approximately mouse ests provided by nia and bmap. as target keywords and go terms we chose those containing the text "brain," "nerv," or "neuro" anywhere in the keyword's or go term's description. we also eliminate by hand keywords describing irrelevant diseases. our target proteins are simply those described by the target keywords and go terms. of the sequences in bmap, can be mapped to proteins using unigene alone. with the est2prot system, biozon maps ests to proteins. as many as ests can be mapped to target proteins. when similarity data is considered the number of ests that can be mapped to target proteins more than doubles to. to demonstrate the utility of the biozon est analysis tool, we used it to determine the potential function of ests identified in a microarray-based screen. this screen was designed to identify genes involved in axon pathfinding and target recognition in the mouse olfactory system. in our preliminary studies we identified thirteen genes that could potentially play key roles in this process. however, eight of these were ests with no known function or annotation. biozon was able to find matches for four of the eight ests. interestingly, one est that is classified to a unigene cluster of unknown function was predicted in biozon to have similarity to protocadherins. protocadherins are members of the cadherin superfamily, and are thought to play key roles in axon guidance, target recognition, and synaptogenesis. our preliminary results suggest that this est is indeed a member of the cadherin superfamily, and may therefore be involved in mediating target recognition within the olfactory system. without such annotation, this est would likely have been ignored, and a valuable potential guidance cue may not have been recognized. other ests that belong to the same unigene cluster as ai are also linked with protocadherins in biozon, through similar paths, although neither unigene nor entrez suggest such links.  to allow biologists to exploit est libraries more efficiently and focus their search more effectively we developed an est mapping system that identifies for each est its most likely protein products. our analysis relies heavily on ncbi's unigene clustering, biozon's infrastructure and the massive protein similarity data contained within. our tool can help experimental biologists filter a large collection of nucleic acid sequences and predict which sequences are germane to a given biological system. as an extensive and established est analysis tool, unigene is our main source of information. biozon augments this data with other datasets that are extracted from multiple databases. for example, unigene uses only model organisms to map est clusters to proteins, while biozon uses protein sequences from thousands of fully or partly sequenced genomes, in addition to a myriad of other biological information on relationships between biological entities to establish multiple paths between est sequences and protein sequences. biozon also analyzes sequences in the ncbi est database that are excluded from the gene-oriented unigene, such as rrna and mitochondiral sequences. the retrieval of this information is done in real-time by traversing paths in the data graph. this is made possible because of the graph-schema of biozon that was designed to handle large-scale integration of dynamically changing biological data, where all datasets are compiled into a single tightly-connected graph. since the data in biozon relies on physical properties rather than just database cross links, the graph-link structure is of high quality. moreover, the biozon database was designed to sustain frequent updates of its sources, and as such it ensures that the mapping utilizes newly sequenced dna and protein sequences. biozon also strives for completeness, and the similarity data makes up for missing and inconsistent data. this has a major impact for example, when compiling the functional descriptors from the go database. since go data is partial, and since it is derived from multiple sources, it is not necessarily coherent. consequently, in many cases proteins that are very similar based on sequence are not necessarily associated with the same set of go terms, and this can greatly reduce the effectiveness of the mapping. by incorporating similarity relations biozon extends and enrich the set of functional descriptors that can be associated with a given est. the est2prot system can be accessed from the biozon webserver. information on the web tools is available in the appendix. availability and requirements est2prot is available online at. any user can upload and analyze her or his est data through any javascript-enabled web browser such as netscape, mozzila or explorer, and obtain the mapping in real-time. authors' contributions ps implemented the est2prot system and ran experiments over the mouse and human genomes. gy and dl conceived of the study. gy designed the system. dl participated in the analysis of the results. all authors contributed, read and approved the final manuscript. supplementary material additional file 1 appendix the est2prot webserver. the appendix takes the reader through the main web pages that make-up the est2prot webserver, with explanations of the output format of each page and snapshots that exemplify the type of information provided. click here for file acknowledgements we thank aaron birkland for his help with the biozon database. this work is supported by the national science foundation under grant no. as part of the nsf/nih collaborative research in computational neuroscience program and by sun microsystems. figures and tables
est2prot extends and significantly enriches the popular unigene mapping by utilizing multiple relations between known biological entities. est libraries are used in various biological studies, from microarray experiments to proteomic and genetic screens. est2prot uses unigene clusters, substring analysis, information about protein coding regions in existing dna sequences and protein database searches to detect protein products related to a query est sequence. consequently, new discoveries are possibly overlooked. the system is part of the biozon database and is accessible at. gene ontology terms, swiss-prot keywords, and protein similarity data are used to map the ests to functional descriptors.
 est libraries are used in various biological studies, from microarray experiments to proteomic and genetic screens. these libraries usually contain many uncharacterized ests that are typically ignored since they cannot be mapped to known genes. consequently, new discoveries are possibly overlooked.  we describe a system that uses multiple elements to map est sequences to their corresponding protein products. est2prot uses unigene clusters, substring analysis, information about protein coding regions in existing dna sequences and protein database searches to detect protein products related to a query est sequence. gene ontology terms, swiss-prot keywords, and protein similarity data are used to map the ests to functional descriptors.  est2prot extends and significantly enriches the popular unigene mapping by utilizing multiple relations between known biological entities. it produces a mapping between ests and proteins in real-time through a simple web-interface. the system is part of the biozon database and is accessible at. 