Programmer: Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
Paper citation and collaborators:
Trait-To-Gene: A Computational Method for Predicting the Function of
Mitchell Levesque, Dennis Shasha, Wook Kim, Michael G. Surette, and Philip
An important use of homology in genomics is to infer the function of unknown genes from well- characterized homologs. However, more refined uses of homology are necessary to identify and annotate the large number of homologous but uncharacterized genes. We have designed a series of algorithms that make functional predictions based on the principles of set theory. Our first analysis detects perfect matches between sets of organisms with a particular trait and sets of homologous genes. Our second set of algorithms utilizes Boolean combinations of genomes and traits to infer gene function. By finding sets of orthologous genes that complement each other in evolutionary lineages, these algorithms predict that other previously uncharacterized, highly conserved genes may be involved in this well-studied pathway. This software is available to the community.
Our software runs in a high performance interpreted environment called K.
bac.k--the main analysis software. It has one internal parameter: the similarity measure threshold is adjusted by changing the value of similarmin to the appropriate level. This can be done by searching for the previous similarmin value and then changing it to the next.
cog.k --which is read by bac.k and parses the cog file
getcogs.k --This reads COG IDs from a constructed
file T (that might have all the COGS having
a given trait) and writes them to two files.
Trows maintains COG arrangements that correspond to the trait.
Tunique is a duplicate-free list of all the COGs that are in Trows.
Run k bac.k (this includes cog.k) It produces tempconclude and temptraitmap the first of which constitute hypotheses about associations between traits and genes on genomes. Post-processing depends on the trait of interest. Suppose we are interested in flagella.
grep "+flagella" temptraitcogs > flagella
grep "perfect" flagella > perfect
grep "similar" flagella > similar
grep "oneneeded" flagella > oneneeded
cp perfect T
This last step produces the files Trows and Tunique corresponding
to perfect correspondences between COGs and flagella.
Repeat the last two steps for similar matches as follows:
cp similar T
Repeat the last two steps again for oneneeded matches as follows:
cp oneneeded T
Caveats: the programs are set to evaluate a specific set of bacteria with their relevant abbreviations. To update the analysis, it is necessary to upload a new cogtxt file from NCBI and then to change the organism abbreviations in bac.k, microorganisms, and cog.k so that they all agree. In addition, in order to update the trait table it is better to fill in trait information for as many genomes as possible.
This material is based upon work partly supported by the United States National Science Foundation under grants IIS-9988636, 0115586, and MCB-0209754. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. This support is greatly appreciated.