Gene Ontology-based semantic alignment of biological pathways by evolutionary search

A large number of biological pathways have been elucidated recently, and there is a need for methods to analyze these pathways. One class of methods compares pathways semantically in order to discover parts that are evolutionarily conserved between species or to discover intraspecies similarities. Such methods usually require that the topologies of the pathways being compared are known, i.e. that a query pathway is being aligned to a model pathway. However, sometimes the query only consists of an unordered set of gene products. Previous methods for mapping sets of gene products onto known pathways have not been based on semantic comparison of gene products using ontologies or other abstraction hierarchies. Therefore, we here propose an approach that uses a similarity function defined in Gene Ontology (GO) terms to find semantic alignments when comparing paths in biological pathways where the nodes are gene products. A known pathway graph is used as a model, and an evolutionary algorithm (EA) is used to evolve putative paths from a set of experimentally determined gene products. The method uses a measure of GO term similarity to calculate a match score between gene products, and the fitness value of each candidate path alignment is derived from these match scores. A statistical test is used to assess the significance of evolved alignments. The performance of the method has been tested using regulatory pathways for S. cerevisiae and M. musculus.