Cargando…

A traveling salesman approach for predicting protein functions

BACKGROUND: Protein-protein interaction information can be used to predict unknown protein functions and to help study biological pathways. RESULTS: Here we present a new approach utilizing the classic Traveling Salesman Problem to study the protein-protein interactions and to predict protein functi...

Descripción completa

Detalles Bibliográficos
Autores principales: Johnson, Olin, Liu, Jing
Formato: Texto
Lenguaje:English
Publicado: BioMed Central 2006
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1636333/
https://www.ncbi.nlm.nih.gov/pubmed/17147783
http://dx.doi.org/10.1186/1751-0473-1-3
_version_ 1782130732669337600
author Johnson, Olin
Liu, Jing
author_facet Johnson, Olin
Liu, Jing
author_sort Johnson, Olin
collection PubMed
description BACKGROUND: Protein-protein interaction information can be used to predict unknown protein functions and to help study biological pathways. RESULTS: Here we present a new approach utilizing the classic Traveling Salesman Problem to study the protein-protein interactions and to predict protein functions in budding yeast Saccharomyces cerevisiae. We apply the global optimization tool from combinatorial optimization algorithms to cluster the yeast proteins based on the global protein interaction information. We then use this clustering information to help us predict protein functions. We use our algorithm together with the direct neighbor algorithm [1] on characterized proteins and compare the prediction accuracy of the two methods. We show our algorithm can produce better predictions than the direct neighbor algorithm, which only considers the immediate neighbors of the query protein. CONCLUSION: Our method is a promising one to be used as a general tool to predict functions of uncharacterized proteins and a successful sample of using computer science knowledge and algorithms to study biological problems.
format Text
id pubmed-1636333
institution National Center for Biotechnology Information
language English
publishDate 2006
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-16363332006-11-29 A traveling salesman approach for predicting protein functions Johnson, Olin Liu, Jing Source Code Biol Med Research BACKGROUND: Protein-protein interaction information can be used to predict unknown protein functions and to help study biological pathways. RESULTS: Here we present a new approach utilizing the classic Traveling Salesman Problem to study the protein-protein interactions and to predict protein functions in budding yeast Saccharomyces cerevisiae. We apply the global optimization tool from combinatorial optimization algorithms to cluster the yeast proteins based on the global protein interaction information. We then use this clustering information to help us predict protein functions. We use our algorithm together with the direct neighbor algorithm [1] on characterized proteins and compare the prediction accuracy of the two methods. We show our algorithm can produce better predictions than the direct neighbor algorithm, which only considers the immediate neighbors of the query protein. CONCLUSION: Our method is a promising one to be used as a general tool to predict functions of uncharacterized proteins and a successful sample of using computer science knowledge and algorithms to study biological problems. BioMed Central 2006-10-12 /pmc/articles/PMC1636333/ /pubmed/17147783 http://dx.doi.org/10.1186/1751-0473-1-3 Text en Copyright © 2006 Johnson and Liu; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License ( (http://creativecommons.org/licenses/by/2.0) ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research
Johnson, Olin
Liu, Jing
A traveling salesman approach for predicting protein functions
title A traveling salesman approach for predicting protein functions
title_full A traveling salesman approach for predicting protein functions
title_fullStr A traveling salesman approach for predicting protein functions
title_full_unstemmed A traveling salesman approach for predicting protein functions
title_short A traveling salesman approach for predicting protein functions
title_sort traveling salesman approach for predicting protein functions
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1636333/
https://www.ncbi.nlm.nih.gov/pubmed/17147783
http://dx.doi.org/10.1186/1751-0473-1-3
work_keys_str_mv AT johnsonolin atravelingsalesmanapproachforpredictingproteinfunctions
AT liujing atravelingsalesmanapproachforpredictingproteinfunctions
AT johnsonolin travelingsalesmanapproachforpredictingproteinfunctions
AT liujing travelingsalesmanapproachforpredictingproteinfunctions