title: Identifying remote protein homologs by network propagation.
abstract: Perhaps the most widely used applications of bioinformatics are tools such as psi-blast for searching sequence databases. We describe a recently developed protein database search algorithm called rankprop. rankprop relies upon a precomputed network of pairwise protein similarities. The algorithm performs a diffusion operation from a specified query protein across the protein similarity network. The resulting activation scores, assigned to each database protein, encode information about the global structure of the protein similarity network. This type of algorithm has a rich history in associationist psychology, artificial intelligence and web search. We describe the rankprop algorithm and its relatives, and we provide evidence that the algorithm successfully improves upon the rankings produced by psi-blast.
authors.affiliation: Department of Genome Sciences Department of Computer Science and Engineering University of Washington Seattle, WA, USA. noble@gs.washington.edu
authors.forename: William S
authors.initials: WS
authors.lastname: Noble
authors.forename: Rui
authors.initials: R
authors.lastname: Kuang
authors.forename: Christina
authors.initials: C
authors.lastname: Leslie
authors.forename: Jason
authors.initials: J
authors.lastname: Weston
mesh_terms: D000465:Algorithms; D001426:Bacterial Proteins / Q000235:genetics; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D020407:Internet; D020283:Photoreceptors, Microbial / Q000235:genetics; D017434:Protein Structure, Tertiary / Q000235:genetics; D011506:Proteins / Q000235:genetics; D012372:ROC Curve; D016415:Sequence Alignment / Q000379:methods*
chemical_list: D001426:Bacterial Proteins; D020283:Photoreceptors, Microbial; D011506:Proteins; C050162:photoactive yellow protein, Bacteria