BACKGROUND
systems biologists aim to understand the dynamic behaviour of cellular pathways with the help of quantitative models.
to construct large-scale models flexibly from existing parts, models need to be retrieved, compared, and combined.
for this purpose, modellers need to find and match equivalent model elements, for instance, variables describing identical metabolites.
in the future, such alignments should be automated or, at least, sensible suggestions should be provided by software.
a simple way to match model elements is by comparing their names or identifiers as they appear in the model's code.
greedy alignments and model combination based on element names have been used in  <cit> , but these approaches may fail if models stem from different sources and therefore use different naming schemes.
a safer and more general approach is to compare model elements by the biological objects or concepts they stand for.
semantic annotations, for instance the miriam-compliant annotations  <cit>  used in the systems biology markup language   <cit> , provide a qualified naming scheme by relating model elements to entries in public web resources or ontologies.
knowledge from these ontologies can be used to compare alike biological objects and to define quantitative similarity scores between them  <cit> .
obviously, such comparisons will fail if annotations are missing.
however, there are also algorithms that compare biological networks by their structures and can therefore handle missing annotations.
since the comparison of graph structures is computationally hard  <cit> , these algorithms either yield approximative results  <cit>  or are restricted to models having a simple structure like a path  <cit>  or a tree  <cit> .
the initial comparison of network nodes, which is later refined using structural information, also varies from approach to approach.
while some of them use plain node labels, others compare nodes by chemical structures  <cit>  or semantic information like ec numbers  <cit>  or gene ontology terms  <cit> .
with this information, they can either refine the alignments  <cit>  or speed up the computations by reducing the search space  <cit> .
a recent review on these and similar works can be found in  <cit> .
in this article, we propose new heuristics for aligning network models with missing annotations.
the basic idea is simple: a reaction, for instance in an sbml model, refers to its substrates and products.
if two reactions are not annotated but their reactants are, we can trace the reactants, evaluate their annotations, and use this information for comparing the reactions.
this logic can be applied whenever model elements show cross-references.
instead of collecting and combining this information step by step for each element, we developed a method to propagate all semantic information simultaneously across the network.
starting from an original direct similarity score, which compares elements only by their own annotations, we obtain a new inferred similarity score that incorporates information obtained from other elements.
two applications of semantic propagation are presented in this article.
the first one is the improved alignment of systems biology models.
the second one is a method for predicting missing annotations in a model by aligning it to fully annotated network models.
our present implementation, which is a part of the tool semanticsbml  <cit> , works for sbml models and for specific similarity measures  <cit> .
however, semantic propagation is a general approach that applies to a wide range of network models and similarity scores and that can be combined with different model matching algorithms, including the ones mentioned above.
RESULTS
algorithm
we have developed methods for aligning partially annotated biological networks and implemented them for sbml models with miriam-compliant annotations.
a model alignment is based on two kinds of knowledge: similarities between model elements, which are computed from semantic annotations, and references between elements within each model .
the alignment of two models is computed in two steps.
in a first step, semantic information is propagated across both network structures.
this ensures that all elements, even elements lacking annotations, obtain semantic information, which makes them comparable between models.
this claim of improved comparability is illustrated with an example of a propagation of "colour information" shown in figure  <dig>  using the network structure, we refine the direct similarity σ and obtain an inferred similarity measure ψ, which can be nonzero even if one of the two compared elements does not carry any annotations.
in the second step, the actual model alignment, elements are matched between two or more models according to their inferred similarities.
we use a greedy heuristic that arranges similar elements into tuples, supposed to be matched: all elements in a tuple have the same type , stem from different models, and each element is part of one tuple .
elements within a tuple have to show a high similarity, while elements in different tuples are supposed to be dissimilar.
feature propagation
the semantic propagation can be carried out in two ways, as feature propagation  or as similarity propagation .
for feature propagation, each element has to be associated with a feature vector.
the components of this vector  describe how closely the element resembles certain biological concepts.
a model species describing a phosphorylated map kinase, for example, could carry annotations referring to uniprot entry p <dig>  and kegg compound entry c <dig> .
the feature vector corresponding to this species would contain mostly zeros except for the two entries specifying the relation to these web resource entries.
two elements are similar if their feature vectors point to similar directions, i.e.
if they are related to similar biological concepts like a phosphorylated and a non-phosphorylated map kinase.
the size of the feature vector depends on the number of biological concepts considered, e.g.
the entries of all web resources being referred to in biomodels database  <cit> .
in feature propagation elements inherit semantic information from their neighbour nodes, which might contribute to the definition of the elements' identity.
the inferred feature vectors do therefore not only characterise the model element itself, but also its surrounding elements in the network.
in the case of a reaction element, they do not only describe the reaction, but also its reactants, enzyme, or regulators.
the transition from the original to the inferred feature vectors is shown by an abstract example in figure 1a.
in this example the colours red, green, and blue correspond to the features in a colour vector of size three, which encode for semantic information.
the propagation of this information  leads to mixed colours in the center of the network, which give each node its own identity and allow for a unique self-alignment of the network.
the mathematical details of feature propagation are explained in the methods section.
similarity propagation
the second approach, similarity propagation, is computationally harder, but also applies to similarity measures that are not based on feature vectors.
in contrast to fp, we do not consider single model elements, but pairs of elements from different models to be compared, e.g.
the reactions x and y from figure 2a.
we require that, if two such elements refer to other elements that share a high similarity, this will increase their own similarity .
our method determines these similarities in a self-consistent manner and uses a propagation process similar to feature propagation.
in contrast to feature propagation the process is not carried out on the reaction network, but on an element pair graph.
in this graph each node represents a pair of elements, one from each model.
two nodes are connected if the corresponding elements are connected in the reaction networks.
the mathematical details are explained in the methods section and a mathematical relation between feature and similarity propagation is discussed in additional file  <dig>
annotation prediction
model alignments can be used to complete missing annotations in a model.
to do so, one may align the model to a large, annotated map of all physiological pathways and copy annotations from elements in the map to the model elements they have been aligned to.
even if not all of these annotations are correct, they may still be presented to users as suggestions during manual model annotation.
our semanticsbml web page for model annotation  provides this functionality and uses biomodels database as a replacement for the large, annotated pathway map.
the idea behind the annotation prediction is to apply feature propagation to a sparsely annotated model and all biomodels.
afterwards, the similarities between non-annotated model elements and all database elements are calculated.
finally, the annotations from the most similar elements contained in the database are presented to the user as suggestions for new annotations.
details of this procedure are described in the methods section.
testing
self-alignment of a linear chain
to illustrate how semantic propagation can improve model alignment, let us consider a linear metabolic pathway in which only the first and the last species are annotated .
if we align two copies of this pathway based on direct similarities, only these two elements can be matched.
with the help of feature propagation or similarity propagation, all reactions and metabolites are matched correctly.
alignment between map kinase pathways
as a real-world example, we aligned two well-annotated signal transduction models, model  <dig>  <cit>  and model  <dig>  <cit>  from biomodels database.
these models contain elements that represent proteins in different phosphorylation states but carry identical annotations.
an alignment based on direct similarities would not be able to distinguish between these different states, but feature propagation and similarity propagation both manage to improve the results .
in practice, models are often less carefully annotated than these example models and the quality of a model alignment will depend on the fraction of annotated elements.
to study this in detail, we considered the same two models, removed some of the annotations in biomodel  <dig> randomly, aligned the models, and scored the quality of the alignments by precision and recall with respect to a manually chosen alignment.
this procedure was repeated  <dig> times for each number of removed annotations.
figure  <dig> shows the results: without semantic propagation, both precision and recall increase almost linearly with the number of annotations present.
this is not surprising because the only possible reason for alignment errors are ambiguities caused by elements carrying identical annotations.
if we use feature or similarity propagation, the quality increases more rapidly.
as expected, the mean recall - i.e.
the fraction of correct matches recovered - is improved because previously incomparable pairs can now be matched.
the precision - counting how many predicted matches are actually correct - depends on how many elements are annotated.
if many annotations have to be guessed, both inferred similarity scores yield a lower precision than the direct similarity.
nevertheless, with a higher number of annotations present, both methods can surpass the simple matching.
sp outperforms fp for both precision and recall, but its computational effort is also much higher.
similar tests with different models lead to similar results .
despite the indifference of the results with respect to the models which are compared, the quality of the results varied in between examples in which only species or reaction annotations had been removed.
the more detailed the annotations in a specific subset of model elements was, the more dramatic the decline in matching quality has been after their removal.
for a deeper analysis of the matching quality after the removal of either species or reaction annotations from biomodel  <dig>  the reader is referred to additional file  <dig>
automatic suggestion of element annotations
in order to test the quality of our annotation prediction heuristic, we applied it to biomodel  <dig>  a well-studied model of glycolysis  <cit> .
for our first evaluation, we removed all annotations from the model and tried to re-predict them via the web interface.
the test confirms that the predictions are not perfect, but the top  <dig> results usually contain relevant annotations.
in general, the predictions become better as the fraction of correctly annotated model elements increases and as we scan more of the top results for the correct annotation.
to study this systematically, we randomly removed annotations from some of the elements, predicted new annotations for them, and checked if the correct annotation appeared in the top results.
as shown in figure  <dig>  a significant number of annotations were predicted correctly using our propagation schemes.
the results suggest that the probability of predicting an annotation correctly increases linearly with the number of annotations present in the model.
considering more of the topmost results did not strongly increase the quality of the prediction.
this shows that correct annotations, if they can be predicted at all, will rank relatively high in the results.
implementation
we have implemented both propagation methods in python.
the source code of this implementation is included in our library semanticsbml, which is freely available  from sourceforge  and can be used to e.g.
annotate and merge sbml models.
furthermore, we have included the semantic propagation methods into our web tool semanticsbml http://www.semanticsbml.org.
first, this web tool allows users to visually compare the results of the three methods to compare model elements .
second, for model merging, all three methods can be used to suggest an initial matching of model elements.
third, for model annotation, new element annotations based on propagated features from biomodels will be suggested after the "predict annotations" button has been clicked.
discussion
annotating the elements of systems biology models is laborious.
interactive software can facilitate this work by keyword searches and by proposing annotations based on element names.
our software semanticsbml  <cit>  helps modellers to annotate and combine sbml models based on miriam-compliant annotations  <cit> .
in the present work, we addressed an important open issue, the alignment of models with missing annotations.
as the examples have shown, element matchings based on our inferred similarity measures perform well in practice.
in our tests, semantic propagation increased the recall of correct element pairs, but at the price of a lower precision if less than half of the elements were annotated.
our two approaches, feature and similarity propagation, differ slightly in their quality, but also in their computational costs.
while similarity propagation tends to yield better results, the computational effort is much higher than in feature propagation  instead of o, where |m| and |n| denote the numbers of elements in the two models).
we furthermore showed how new annotations for model elements can be suggested based on the annotations already present in a model and an annotated pathway map.
for our predictions, we have selected the biomodels database as a resource for highly curated annotation data.
analyses using other resources  show no loss in prediction quality and we plan to extend our background pathway map by using various other pathway resources in the future.
the details on how information is transfered during semantic propagation depends on the choice of propagation weights.
in our tests, changing their values within reasonable ranges had little influence on the model alignment.
in any case, the scaling factor λ  allowed to avoid an overly strong propagation, which might lead to spurious similarities.
as soon as a sufficient number of predefined model matchings will be available as a gold standard, the propagation weights may be further improved by machine learning.
CONCLUSIONS
compared to existing approaches, our methods for model alignment have three advantages.
first, by processing semantic annotations instead of ad-hoc node labels, we can compare models from different sources and compare elements with similar, yet different annotations.
second, considering the network structure allows us to distinguish between model elements carrying identical annotations, e.g.
proteins in different phosphorylation states.
third, our similarity measures can be combined with various structure-based model comparison algorithms, e.g.
<cit> .
although our approach has only been implemented for sbml models, it can be extended to any computational models that include structural information and semantic annotations.

 systems biologists aim to understand the dynamic behaviour of cellular pathways with the help of quantitative models. to construct large-scale models flexibly from existing parts, models need to be retrieved, compared, and combined. for this purpose, modellers need to find and match equivalent model elements, for instance, variables describing identical metabolites. in the future, such alignments should be automated or, at least, sensible suggestions should be provided by software. a simple way to match model elements is by comparing their names or identifiers as they appear in the model's code. greedy alignments and model combination based on element names have been used in, but these approaches may fail if models stem from different sources and therefore use different naming schemes. a safer and more general approach is to compare model elements by the biological objects or concepts they stand for. semantic annotations, for instance the miriam-compliant annotations used in the systems biology markup language, provide a qualified naming scheme by relating model elements to entries in public web resources or ontologies. knowledge from these ontologies can be used to compare alike biological objects and to define quantitative similarity scores between them. obviously, such comparisons will fail if annotations are missing. however, there are also algorithms that compare biological networks by their structures and can therefore handle missing annotations. since the comparison of graph structures is computationally hard, these algorithms either yield approximative results or are restricted to models having a simple structure like a path or a tree. the initial comparison of network nodes, which is later refined using structural information, also varies from approach to approach. while some of them use plain node labels, others compare nodes by chemical structures or semantic information like ec numbers or gene ontology terms. with this information, they can either refine the alignments or speed up the computations by reducing the search space. a recent review on these and similar works can be found in. in this article, we propose new heuristics for aligning network models with missing annotations. the basic idea is simple: a reaction, for instance in an sbml model, refers to its substrates and products. if two reactions are not annotated but their reactants are, we can trace the reactants, evaluate their annotations, and use this information for comparing the reactions. this logic can be applied whenever model elements show cross-references. instead of collecting and combining this information step by step for each element, we developed a method to propagate all semantic information simultaneously across the network. starting from an original direct similarity score, which compares elements only by their own annotations, we obtain a new inferred similarity score that incorporates information obtained from other elements. two applications of semantic propagation are presented in this article. the first one is the improved alignment of systems biology models. the second one is a method for predicting missing annotations in a model by aligning it to fully annotated network models. our present implementation, which is a part of the tool semanticsbml, works for sbml models and for specific similarity measures. however, semantic propagation is a general approach that applies to a wide range of network models and similarity scores and that can be combined with different model matching algorithms, including the ones mentioned above.  algorithm we have developed methods for aligning partially annotated biological networks and implemented them for sbml models with miriam-compliant annotations. a model alignment is based on two kinds of knowledge: similarities between model elements, which are computed from semantic annotations, and references between elements within each model. the alignment of two models is computed in two steps. in a first step, semantic information is propagated across both network structures. this ensures that all elements, even elements lacking annotations, obtain semantic information, which makes them comparable between models. this claim of improved comparability is illustrated with an example of a propagation of "colour information" shown in figure using the network structure, we refine the direct similarity σ and obtain an inferred similarity measure ψ, which can be nonzero even if one of the two compared elements does not carry any annotations. in the second step, the actual model alignment, elements are matched between two or more models according to their inferred similarities. we use a greedy heuristic that arranges similar elements into tuples, supposed to be matched: all elements in a tuple have the same type, stem from different models, and each element is part of one tuple. elements within a tuple have to show a high similarity, while elements in different tuples are supposed to be dissimilar. feature propagation the semantic propagation can be carried out in two ways, as feature propagation or as similarity propagation. for feature propagation, each element has to be associated with a feature vector. the components of this vector describe how closely the element resembles certain biological concepts. a model species describing a phosphorylated map kinase, for example, could carry annotations referring to uniprot entry p and kegg compound entry c. the feature vector corresponding to this species would contain mostly zeros except for the two entries specifying the relation to these web resource entries. two elements are similar if their feature vectors point to similar directions, i.e. if they are related to similar biological concepts like a phosphorylated and a non-phosphorylated map kinase. the size of the feature vector depends on the number of biological concepts considered, e.g. the entries of all web resources being referred to in biomodels database. in feature propagation elements inherit semantic information from their neighbour nodes, which might contribute to the definition of the elements' identity. the inferred feature vectors do therefore not only characterise the model element itself, but also its surrounding elements in the network. in the case of a reaction element, they do not only describe the reaction, but also its reactants, enzyme, or regulators. the transition from the original to the inferred feature vectors is shown by an abstract example in figure 1a. in this example the colours red, green, and blue correspond to the features in a colour vector of size three, which encode for semantic information. the propagation of this information leads to mixed colours in the center of the network, which give each node its own identity and allow for a unique self-alignment of the network. the mathematical details of feature propagation are explained in the methods section. similarity propagation the second approach, similarity propagation, is computationally harder, but also applies to similarity measures that are not based on feature vectors. in contrast to fp, we do not consider single model elements, but pairs of elements from different models to be compared, e.g. the reactions x and y from figure 2a. we require that, if two such elements refer to other elements that share a high similarity, this will increase their own similarity. our method determines these similarities in a self-consistent manner and uses a propagation process similar to feature propagation. in contrast to feature propagation the process is not carried out on the reaction network, but on an element pair graph. in this graph each node represents a pair of elements, one from each model. two nodes are connected if the corresponding elements are connected in the reaction networks. the mathematical details are explained in the methods section and a mathematical relation between feature and similarity propagation is discussed in additional file annotation prediction model alignments can be used to complete missing annotations in a model. to do so, one may align the model to a large, annotated map of all physiological pathways and copy annotations from elements in the map to the model elements they have been aligned to. even if not all of these annotations are correct, they may still be presented to users as suggestions during manual model annotation. our semanticsbml web page for model annotation provides this functionality and uses biomodels database as a replacement for the large, annotated pathway map. the idea behind the annotation prediction is to apply feature propagation to a sparsely annotated model and all biomodels. afterwards, the similarities between non-annotated model elements and all database elements are calculated. finally, the annotations from the most similar elements contained in the database are presented to the user as suggestions for new annotations. details of this procedure are described in the methods section. testing self-alignment of a linear chain to illustrate how semantic propagation can improve model alignment, let us consider a linear metabolic pathway in which only the first and the last species are annotated. if we align two copies of this pathway based on direct similarities, only these two elements can be matched. with the help of feature propagation or similarity propagation, all reactions and metabolites are matched correctly. alignment between map kinase pathways as a real-world example, we aligned two well-annotated signal transduction models, model and model from biomodels database. these models contain elements that represent proteins in different phosphorylation states but carry identical annotations. an alignment based on direct similarities would not be able to distinguish between these different states, but feature propagation and similarity propagation both manage to improve the results. in practice, models are often less carefully annotated than these example models and the quality of a model alignment will depend on the fraction of annotated elements. to study this in detail, we considered the same two models, removed some of the annotations in biomodel randomly, aligned the models, and scored the quality of the alignments by precision and recall with respect to a manually chosen alignment. this procedure was repeated times for each number of removed annotations. figure shows the results: without semantic propagation, both precision and recall increase almost linearly with the number of annotations present. this is not surprising because the only possible reason for alignment errors are ambiguities caused by elements carrying identical annotations. if we use feature or similarity propagation, the quality increases more rapidly. as expected, the mean recall - i.e. the fraction of correct matches recovered - is improved because previously incomparable pairs can now be matched. the precision - counting how many predicted matches are actually correct - depends on how many elements are annotated. if many annotations have to be guessed, both inferred similarity scores yield a lower precision than the direct similarity. nevertheless, with a higher number of annotations present, both methods can surpass the simple matching. sp outperforms fp for both precision and recall, but its computational effort is also much higher. similar tests with different models lead to similar results. despite the indifference of the results with respect to the models which are compared, the quality of the results varied in between examples in which only species or reaction annotations had been removed. the more detailed the annotations in a specific subset of model elements was, the more dramatic the decline in matching quality has been after their removal. for a deeper analysis of the matching quality after the removal of either species or reaction annotations from biomodel the reader is referred to additional file automatic suggestion of element annotations in order to test the quality of our annotation prediction heuristic, we applied it to biomodel a well-studied model of glycolysis. for our first evaluation, we removed all annotations from the model and tried to re-predict them via the web interface. the test confirms that the predictions are not perfect, but the top results usually contain relevant annotations. in general, the predictions become better as the fraction of correctly annotated model elements increases and as we scan more of the top results for the correct annotation. to study this systematically, we randomly removed annotations from some of the elements, predicted new annotations for them, and checked if the correct annotation appeared in the top results. as shown in figure a significant number of annotations were predicted correctly using our propagation schemes. the results suggest that the probability of predicting an annotation correctly increases linearly with the number of annotations present in the model. considering more of the topmost results did not strongly increase the quality of the prediction. this shows that correct annotations, if they can be predicted at all, will rank relatively high in the results. implementation we have implemented both propagation methods in python. the source code of this implementation is included in our library semanticsbml, which is freely available from sourceforge and can be used to e.g. annotate and merge sbml models. furthermore, we have included the semantic propagation methods into our web tool semanticsbml http://www.semanticsbml.org. first, this web tool allows users to visually compare the results of the three methods to compare model elements. second, for model merging, all three methods can be used to suggest an initial matching of model elements. third, for model annotation, new element annotations based on propagated features from biomodels will be suggested after the "predict annotations" button has been clicked. discussion annotating the elements of systems biology models is laborious. interactive software can facilitate this work by keyword searches and by proposing annotations based on element names. our software semanticsbml helps modellers to annotate and combine sbml models based on miriam-compliant annotations. in the present work, we addressed an important open issue, the alignment of models with missing annotations. as the examples have shown, element matchings based on our inferred similarity measures perform well in practice. in our tests, semantic propagation increased the recall of correct element pairs, but at the price of a lower precision if less than half of the elements were annotated. our two approaches, feature and similarity propagation, differ slightly in their quality, but also in their computational costs. while similarity propagation tends to yield better results, the computational effort is much higher than in feature propagation instead of o, where |m| and |n| denote the numbers of elements in the two models). we furthermore showed how new annotations for model elements can be suggested based on the annotations already present in a model and an annotated pathway map. for our predictions, we have selected the biomodels database as a resource for highly curated annotation data. analyses using other resources show no loss in prediction quality and we plan to extend our background pathway map by using various other pathway resources in the future. the details on how information is transfered during semantic propagation depends on the choice of propagation weights. in our tests, changing their values within reasonable ranges had little influence on the model alignment. in any case, the scaling factor λ allowed to avoid an overly strong propagation, which might lead to spurious similarities. as soon as a sufficient number of predefined model matchings will be available as a gold standard, the propagation weights may be further improved by machine learning.  compared to existing approaches, our methods for model alignment have three advantages. first, by processing semantic annotations instead of ad-hoc node labels, we can compare models from different sources and compare elements with similar, yet different annotations. second, considering the network structure allows us to distinguish between model elements carrying identical annotations, e.g. proteins in different phosphorylation states. third, our similarity measures can be combined with various structure-based model comparison algorithms, e.g.. although our approach has only been implemented for sbml models, it can be extended to any computational models that include structural information and semantic annotations. 
one may either propagate feature vectors, describing the annotations of individual elements, or quantitative similarities between elements from different models. a new method called "semantic propagation" allows the comparison of model elements based not only on their own annotations, but also on annotations of surrounding elements in the network. based on semantic propagation, we align partially annotated models and find annotations for non-annotated model elements. semantic propagation and model alignment are included in the open-source library semanticsbml, available on sourceforge. online services for model alignment and for annotation prediction can be used at http://www.semanticsbml.org. to enable automatic searches, alignments, and model combination, the elements of systems biology models need to be compared and matched across models.
 to enable automatic searches, alignments, and model combination, the elements of systems biology models need to be compared and matched across models. elements can be identified by machine-readable biological annotations, but assigning such annotations and matching non-annotated elements is tedious work and calls for automation.  a new method called "semantic propagation" allows the comparison of model elements based not only on their own annotations, but also on annotations of surrounding elements in the network. one may either propagate feature vectors, describing the annotations of individual elements, or quantitative similarities between elements from different models. based on semantic propagation, we align partially annotated models and find annotations for non-annotated model elements.  semantic propagation and model alignment are included in the open-source library semanticsbml, available on sourceforge. online services for model alignment and for annotation prediction can be used at http://www.semanticsbml.org. 