title: Metabolic network prediction through pairwise rational kernels.
abstract: BACKGROUND
  Metabolic networks are represented by the set of metabolic pathways. Metabolic pathways are a series of biochemical reactions, in which the product (output) from one reaction serves as the substrate (input) to another reaction. Many pathways remain incompletely characterized. One of the major challenges of computational biology is to obtain better models of metabolic pathways. Existing models are dependent on the annotation of the genes. This propagates error accumulation when the pathways are predicted by incorrectly annotated genes. Pairwise classification methods are supervised learning methods used to classify new pair of entities. Some of these classification methods, e.g., Pairwise Support Vector Machines (SVMs), use pairwise kernels. Pairwise kernels describe similarity measures between two pairs of entities. Using pairwise kernels to handle sequence data requires long processing times and large storage. Rational kernels are kernels based on weighted finite-state transducers that represent similarity measures between sequences or automata. They have been effectively used in problems that handle large amount of sequence information such as protein essentiality, natural language processing and machine translations.
  
  
  RESULTS
  We create a new family of pairwise kernels using weighted finite-state transducers (called Pairwise Rational Kernel (PRK)) to predict metabolic pathways from a variety of biological data. PRKs take advantage of the simpler representations and faster algorithms of transducers. Because raw sequence data can be used, the predictor model avoids the errors introduced by incorrect gene annotations. We then developed several experiments with PRKs and Pairwise SVM to validate our methods using the metabolic network of Saccharomyces cerevisiae. As a result, when PRKs are used, our method executes faster in comparison with other pairwise kernels. Also, when we use PRKs combined with other simple kernels that include evolutionary information, the accuracy values have been improved, while maintaining lower construction and execution times.
  
  
  CONCLUSIONS
  The power of using kernels is that almost any sort of data can be represented using kernels. Therefore, completely disparate types of data can be combined to add power to kernel-based machine learning methods. When we compared our proposal using PRKs with other similar kernel, the execution times were decreased, with no compromise of accuracy. We also proved that by combining PRKs with other kernels that include evolutionary information, the accuracy can also also be improved. As our proposal can use any type of sequence data, genes do not need to be properly annotated, avoiding accumulation errors because of incorrect previous annotations.
authors.affiliation: Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada. aroche@cs.umanitoba.ca.
authors.forename: Abiel
authors.initials: A
authors.lastname: Roche-Lima
authors.forename: Michael
authors.initials: M
authors.lastname: Domaratzki
authors.forename: Brian
authors.initials: B
authors.lastname: Fristensky
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D053858:Metabolic Networks and Pathways; D012441:Saccharomyces cerevisiae / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism; D012984:Software; D060388:Support Vector Machine
chemical_list: D029701:Saccharomyces cerevisiae Proteins