Protein function annotation based on ortholog clusters extracted from incomplete genomes using combinatorial optimization

Reliable automatic protein function annotation requires methods for detecting orthologs with known function from closely related species. While current approaches are restricted to finding ortholog clusters from complete proteomes, most annotation problems arise in the context of partially sequenced genomes. We use a combinatorial optimization method for extracting candidate ortholog clusters robustly from incomplete genomes. The proposed algorithm focuses exclusively on sequence relationships across genomes and finds a subset of sequences from multiple genomes where every sequence is highly similar to other sequences in the subset. We then use an optimization criterion similar to the one for finding ortholog clusters to annotate the target sequences. We report on a candidate annotation for proteins in the rice genome using ortholog clusters constructed from four partially complete cereal genomes - barley, maize, sorghum, wheat and the complete genome of Arabidopsis.