Building ancestral recombination graphs (ARGs) with the minimum number of recombination events is an essential problem in genomic population studies. Exhaustive search methods have been proposed to solve the problem with few sequences and markers. Recently, we introduced ARG4WG algorithm [1] to build plausible ARGs for whole genomes of thousand samples. However, the ARG4WG algorithm was not designed to optimize the number of recombination events. In this work, we propose a new design of the ARG4WG algorithm to optimize the number of recombination events. The key idea is to analyze and combine different criteria (i.e., the longest shared ends, the maximum similarity between sequences, and the length of sequences) to select the best candidates for recombinations. The experiments on different data sets showed that our new algorithms produced ARGs with smaller number of recombination events in comparison to other methods. The methods allow us to build minimum recombination ARGs from whole genome data sets.
展开▼
