Homology of highly divergent genes often cannot be determined from sequence similarity alone. For example, we recently identified in Hormaphis cornu a family of rapidly evolving bicycle genes, which encode novel proteins implicated as plant gall effectors. Sequence similarity search methods yielded few putative bicycle homologs in other species. 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. We found that a linear logistic regression classifier using only structural features of bicycle genes identified many putative bicycle homologs in other species. Independent evidence from sequence features and intron locations supported homology assignments. To test the potential roles of bicycle genes in other aphids, we sequenced the genome of a second gall- forming aphid, Tetraneura ulmi, and found that many bicycle genes are strongly expressed in the salivary glands of the gall forming foundress. In addition, bicycle genes are strongly overexpressed in the salivary glands of a non-gall forming aphid, Acyrthosiphon pisum, and in the non-gall forming generations of Hormaphis cornu. These observations suggest that 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.