Dynamic contrast-enhanced MRI (DCE-MRI) images are increasingly used for assessing cancer treatment outcome. These time sequences are typically affected by motion, which causes significant errors in tracer kinetic model analysis. Current intra-sequence registration methods for contrast enhanced data either assume restricted transformations (e.g. translation) or employ continuous optimization, which is prone to local optima. In this work, we propose a new approach to DCE-MRI intra-sequence registration and pharmacokinetic modelling, which is formulated in an MRF optimization framework. The complete 4D graph corresponding to a DCE-MRI sequence is reduced to a concatenation of minimum spanning trees, which can be optimized more efficiently. To address the changes due to contrast, a data cost function which incorporates pharmacokinetic modelling information is formulated. The advantages of this method are demonstrated on 8 DCE-MRI image sequences of patients with advanced rectal tumours, presenting mild to severe motion.