Motif-based protein ranking by network propagation.
BACKGROUND
Sequence similarity often suggests evolutionary relationships between protein sequences that can be important for inferring similarity of structure or function. The most widely-used pairwise sequence comparison algorithms for homology detection, such as BLAST and PSI-BLAST, often fail to detect less conserved remotely-related targets.


RESULTS
In this paper, we propose a new general graph-based propagation algorithm called MotifProp to detect more subtle similarity relationships than pairwise comparison methods. MotifProp is based on a protein-motif network, in which edges connect proteins and the k-mer based motif features that they contain. We show that our new motif-based propagation algorithm can improve the ranking results over a base algorithm, such as PSI-BLAST, that is used to initialize the ranking. Despite the complex structure of the protein-motif network, MotifProp can be easily interpreted using the top-ranked motifs and motif-rich regions induced by the propagation, both of which are helpful for discovering conserved structural components in remote homologies.
Kuang
Rui
R
Department of Computer Science, Columbia University New York, NY 10027, USA.
Weston
Jason
J
Noble
William Stafford
WS
Leslie
Christina
C
D000465:Algorithms; D020816:Amino Acid Motifs; D000595:Amino Acid Sequence; D003198:Computer Simulation; D008956:Models, Chemical; D008958:Models, Molecular; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods; D011506:Proteins / Q000032:analysis / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid
D011506:Proteins