The rapid accumulation of whole-genome data has renewed interest in the study of 
genomic rearrangements. Comparative genomics, evolutionary biology, and cancer 
research all require models and algorithms to elucidate the mechanisms, history, 
and consequences of these rearrangements. However, even simple models lead to 
NP-hard problems, particularly in the area of phylogenetic analysis. Current 
approaches are limited to small collections of genomes and low-resolution data 
(typically a few hundred syntenic blocks). Moreover, whereas phylogenetic 
analyses from sequence data are deemed incomplete unless bootstrapping scores (a 
measure of confidence) are given for each tree edge, no equivalent to 
bootstrapping exists for rearrangement-based phylogenetic analysis. We describe 
a fast and accurate algorithm for rearrangement analysis that scales up, in both 
time and accuracy, to modern high-resolution genomic data. We also describe a 
novel approach to estimate the robustness of results-an equivalent to the 
bootstrapping analysis used in sequence-based phylogenetic reconstruction. We 
present the results of extensive testing on both simulated and real data showing 
that our algorithm returns very accurate results, while scaling linearly with 
the size of the genomes and cubically with their number. We also present 
extensive experimental results showing that our approach to robustness testing 
provides excellent estimates of confidence, which, moreover, can be tuned to 
trade off thresholds between false positives and false negatives. Together, 
these two novel approaches enable us to attack heretofore intractable problems, 
such as phylogenetic inference for high-resolution vertebrate genomes, as we 
demonstrate on a set of six vertebrate genomes with 8,380 syntenic blocks. A 
copy of the software is available on demand.