Homology of highly divergent genes often cannot be determined from sequence similarity alone. Coding sequence-independent features of genes, such as intron-exon boundaries, often evolve more slowly than coding sequences, however, and can provide complementary evidence for homology. For example, we recently identified in the aphid Hormaphis cornu a family of rapidly evolving bicycle genes, which encode novel proteins implicated as plant gall effectors, and sequence similarity search methods yielded few putative bicycle homologs in other species. We found that a linear logistic regression classifier using only structural features of bicycle genes identified many putative bicycle homologs in widely divergent Homopteran species. Independent evidence from sequence features and intron locations supported homology assignments. Bicycle proteins may be used by multiple aphid species to manipulate plants in diverse ways. Incorporation of gene structural features into sequence search algorithms may aid identification of deeply divergent homologs, especially of rapidly evolving genes involved in host-parasite interactions.