Whole metagenome shotgun sequencing is a powerful approach for assaying the functional potential of microbial communities. Presently, we lack tools that efficiently and accurately align DNA reads against protein references, the technique necessary for constructing a functional profile. Here, we present PALADIN—a novel modification of Burrows-Wheeler Aligner that provides more accurate alignment and orders-of-magnitude improved efficiency by directly mapping in protein space.