This book constitutes the refereed proceedings of the 4th RECOMB Comparative Genomics Satellite Workshop, RECOMB-CG 2006. The 17 revised full papers presented were carefully reviewed and selected from 34 initial submissions. The papers address a broad variety of aspects and components of the field of comparative genomics, ranging from new quantitative discoveries about genome structure and process to theorems on the complexity of computational problems inspired by genome comparison.