We present the NML model for classes of models with memory described by first order dependencies. The model is used for efficiently locating and encoding the best regressor present in a dictionary. By combining the order-1 NML with the order- 0 NML model the resulting algorithm achieves a consistent improvement over the earlier order-0 NML algorithm, and it is demonstrated to have superior performance on the practical compression of the human genome.