On the accurate construction of consensus genetic maps

Yonghui Wu, Timothy J. Close, Stefano Lonardi*

Department of Computer Science and Engineering, University of California, RIverside, CA 92521, USA. stelo@cs.ucr.edu

Proc LSS Comput Syst Bioinform Conf. August, 2008. Vol. 7, p. 285-296. Full-Text PDF

*To whom correspondence should be addressed.

We study the problem of merging genetic maps, when the individual genetic maps are given as directed acyclic graphs. The problem is to build a consensus map, which includes and is consistent with all (or, the vast majority of) the markers in the individual maps. When markers in the input maps have ordering conflicts, the resulting consensus map will contain cycles. We formulate the problem of resolving cycles in a combinatorial optimization framework, which in turn is expressed as an integer linear program. A faster approximation algorithm is proposed, and an additional speed-up heuristic is developed. According to an extensive set of experimental results, our tool is consistently better than JOINMAP, both in terms of accuracy and running time.