Constructing comparative genome maps with unresolved marker order

Comparative genome maps are a powerful tool for interpreting the genomes of related organisms. The species maps which are the input to the process of constructing comparative maps are often themselves constructed from incomplete or inconsistent data, resulting in markers (or genes) whose order is not fully resolved. This incomplete marker order information is often handled by placing markers whose relative order cannot be reliably inferred together in a bin which is mapped to a common location. Previous automated and manual methods have handled such markers in an ad hoc or arbitrary way. We present efficient algorithms for comparative map construction that provide a principled method for handling unresolved marker order. The algorithms are based on a technique for efficiently computing a marker order that optimizes a natural parsimony criterion; in this way, they also yield a working hypothesis about the original incomplete data set.