Abstract: The recent sequencing of multiple eukaryotic genomes offers an unprecedented opportunity to study the evolution of genomic elements like protein coding genes. The initial step in any such study is to obtain accurate gene annotations. Lack of sufficient experimental evidence necessitates the development of computational annotation tools. This thesis presents algorithms for genome annotation and their applications for studying gene evolution. We first develop a Gibbs sampling approach for ab-initio identification of genes in multiple orthologous sequences. This approach leverages the evolutionary relationships between the sequences to improve the gene predictions, without explicitly aligning the sequences. We show that excellent performance can be obtained with as little as four organisms. The method overcomes a number of difficulties of previous comparison based gene finding approaches: it is robust with respect to genomic rearrangements, can work with draft sequence, and is fast (linear in the number and length of the sequences). We also develop GeneMapper, a program for transferring annotations from a well annotated genome to other genomes. Drawing on high quality curated annotations, GeneMapper enables rapid and accurate annotation of newly sequenced genomes and is suitable for both finished and draft genomes. GeneMapper uses a profile based approach for mapping genes into multiple species, improving upon the standard pairwise approach. Finally, these methods are employed to annotate the newly available fruitfly and mammalian genomic sequences. We use these annotations to study the evolution of gene structure through intron gain and loss. We test several previously proposed mechanisms of intron gain and loss. We also study the relationship between intron loss and duplication events. We find that although gene duplication is highly correlated with intron loss, structural changes in genes are not necessarily due to a loss of constraint following gene duplication as previously suggested.