INFERRING GENOME-WIDE MOSAIC STRUCTURE QI ZHANG, WEI WANG, LEONARD MCMILLAN, FERNANDO PARDO-MANUEL DE VILLENA, DAVID THREADGILL University of North Carolina at Chapel Hil l Genetic recombination plays two essential biological roles. It ensures the fidelity of the transmission of genetic information from one generation to the next and it generates new combinations of genetic variants. Therefore, recombination is a critical process in shaping arrangement of p olymorphisms within p opulations. "Recombination breakp oints" in a given set of genomes from individuals in a p opulation divide the genome into haplotyp e blocks, resulting in a mosaic structure on the genome. In this pap er, we study the Minimum Mosaic Problem: given a set of genome sequences from individuals within a p opulation, compute a mosaic structure containing the minimum numb er of breakp oints. This mosaic structure provides a good estimation of the minimum numb er of recombination events (and their location) required to generate the existing haplotyp es in the p opulation. We solve this problem by finding the shortest path in a directed graph. Our algorithm's efficiency p ermits genome-wide analysis. 1. Intro duction Ancestral genetic recombination events play a critical role in shaping extant genomes. Characterizing the patterns of recombination (e.g . the recombination locations and rates), is a crucial step for reconstructing evolutionary histories, performing disease association mapping, and solving other population genetics problems. During meiosis diploid organisms recombine two homologous genome copies on a chromosome by chromosome basis to form a haploid gamete, which contributes half of the genetic content to its offspring. This mixing of genomes leads to mosaic chromosome (haplotype) structure composed of segments from each grandparent. We refer to the boundaries between the segments of each haplotype as the recombination breakpoints in this paper. Recombination breakpoints represent locations where the crossovers have occurred, either during the generation of the haplotype itself, or in previous generations. In this paper, we are interested in inferring the possible mosaic structure of a given set of related haplotypes. This is accomplished by finding a set of recombination breakpoints that divide the haplotypes into compatible blocks according to the Four-Gamete Test (FGT)? . The FGT states that, under the infinite-sites assumption? , all pairs of polymorphisms should cooccur in only three out of their four possible configurations. Thus, when four configurations are observed in a pair of markers, it implies that either a recombination or a homoplastic event has occurred between them. We propose an efficient algorithm to solve the "Minimum Mosaic Problem", which finds the mosaic with the minimum number of breakpoints. The algorithm is suitable for genome-wide study. 2. Related Work Many algorithms have been developed for estimating a lower bound on the minimum number of recombination events necessary to generate a given set of haplotypes. Hudson and Kaplan? proposed a lower bound (HK bound) computed using the FGT? . Their algorithm computes a minimum set of non-overlapping intervals where all pairs of SNPs in an interval are compatible according to the FGT. This number of intervals, less one, is the HK bound. Myers and Griffiths? proposed a tighter bound, RecMin. However, it is only computationally tractable to find the optimal RecMin in relatively small data sets. Myer and Song et al.? proposed a RecMin approximation algorithm known as HapBound using Integer Linear Programming (ILP). They also proposed an algorithm, SHRUB, which finds a plausible evolutional history for the given haplotypes, called an Ancestral Recombination Graph (ARG). The ARG establishes an upper-bound on the minimum number of recombinations. Different from RecMin or SHRUB, our algorithm focuses on the mosaic structure of a set of sample sequences without explicitly computing the evolutionary history, assuming that the genomic structures of the sample sequences are of more interest. However, the breakpoints on the sample sequences may reflect possible recombination events happened in the history. In addition to estimating lower-bounds on the number of recombinations, algorithms have also been proposed for finding a set of founders which generate a given set of recombinant sequences. Ukkonen first proposed the founder set reconstruction problem ? . A dynamic programming algorithm was developed to compute a minimum number of founders with a given set of sample haplotype sequences, where a segmentation of all the sequences in the sample set can be derived which contains the minimum number of segments. Wu and Gusfield ? studied a slightly different problem to compute a set of K founders where a segmentation of the given sequences can be derived with a minimum number of segments. They proposed a polynomial time algorithm for genotype sample sequences with only two founders. Different from these works, we do not construct the founder sequences, or rely on the existence of a founder set for segmentation and inferring the mosaic structures on the genome. 3. Problem Formulation Suppose that we have a set of n haplotypes over m SNPs, represented by a binary data matrix D = [dij ]i=1..n,j =1..m . Row i in D corresponds to a haplotype hi , and column j in D corresponds to a SNP sj . Matrix entry dij is either 0 or 1, representing the ma jority allele or minority allele at SNP sj respectively. In this paper, we only consider crossover recombination events, ignoring gene conversion and homoplasy (assuming they do not have a significant role). Over any pair of SNPs sj and sj , a haplotype takes one of four possible gametes 00, 01, 10, 11 (the combination of alleles at sj and sj ). We denote the set of haplotypes taking 00, 01, 10, or 11 at SNP pair (sj , sj ) j j j j as H apS etj,0 , H apS etj,1 , H apS etj,0 , H apS etj,1 respectively. If all four 1 1 0 0 sets are nonempty, according to the FGT? , a historical recombination event must have occurred between sj and sj . In this case, we say that the SNP pair (sj , sj ) is incompatible. We represent a recombination breakpoint as a tuple (hi , sb ), where the breakpoint locates on haplotype hi between SNPs sb and sb+1 . It is possible that multiple haplotypes may have breakpoints at the same location since they may "inherit" the breakpoint from a common ancestor sequence. We define a compatible block of SNPs as a continuous set of SNPs such that any two SNPs inside the block are compatible. Two SNP blocks are incompatible with each other if there exist two incompatible SNPs, one from each block. A complete set of breakpoints creates a haplotype mosaic structure over the set of genome sequences. A Mosaic M over a SNP data matrix D is defined as a set of recombination breakpoints M = {(hi , sb )}, i [1, n], b [1, m]. The set of distincta locations of breakpoints sb in M divides the entire range of SNPs [s1 , sm ] into blocks that satisfy: 1) each block is a a Multiple breakp oints can corresp ond to the same sb compatible block, 2) any two neighboring blocks are incompatible, and 3) any two neighboring blocks (assume the boundary is between sb and sb+1 ) would become compatible if the set of haplotypes that have breakpoints between sb and sb+1 are excluded. In this paper, we develop an efficient algorithm for computing Minimum Mosaic (denoted as Mmin ) ­ the mosaic structure that contains the least number of breakpoints. We refer to this problem as the Minimum Mosaic Problem. 4. Inferring the Lo cal Mosaic 4.1. Maximal Intervals We begin by defining the concept of maximal interv al. An interv al I = [sb , se ] is a set of consecutive SNPs which are compatible with each other starting from sb and ending at se . We define an interval I as a maximal interv al if and only if there is no other interval I , I = I , I = [s , s ], which be contains I : s sb , and s se . The complete set of maximal intervals e b can be computed in O(mn) time? , assuming that the compatibility test of any two SNPs using FGT takes O(1) time? . 4.2. Finding Local Breakpoints Maximal intervals are useful for inferring the local mosaic. The set of distinct breakpoint locations sb in a mosaic M = {(hi , sb )} divide the entire SNP range [s1 , sm ] into compatible blocks, where neighboring blocks are incompatible. The set of breakpoints in M is the union of the set of breakpoints on the boundary of each pair of neighboring blocks. We first consider the breakpoints on the boundary of a pair of neighboring blocks. We observe that, every pair of neighboring blocks in M fall inside a pair of overlapping or adjacent maximal intervals, as stated in the following Lemma: Lemma 4.1. For any pair of neighboring blocks (BL , BR ) deduced by a mosaic, there exists a pair of overlapping or adjacent maximal intervals (IL , IR ), where BL completely fal ls inside IL (BL IL ) but not IR (BL \IR = ), and BR completely fal ls inside IR (BR IR ) but not IL (BR \IL = ). We refer to (IL , IR ) as (BL , BR )'s containing interval pair; and (BL , BR ) as (IL , IR )'s contained block pair (Fig. 1). Pro of. Haplotypes Haplotypes IL IR IL IR BL SNPs BR BL SNPs BR (a) IL and IR are overlapping (b) IL and IR are adjacent Figure 1. Neighb oring blocks BL , BR fall inside overlapping/adjacent maximal intervals IL , IR resp ectively. The dots in the shaded region represent incompatible SNP pairs of IL and IR . Details of the proof are presented in ? . For each pair of overlapping or adjacent intervals (IL , IR ), there exists a set of incompatible SNP pairs SNPPair (IL , IR ) = {(sl , sr )}, where l < r, sl and sr are incompatible, and sl IL \IR , sr IR \IL . For example, in Fig. 1(a) and 1(b), each dot represents an incompatible SNP pair. Let (BL , BR ) be a contained block pair of the interval pair (IL , IR ). We denote the incompatible SNP pairs contained in (BL , BR ) as SNPPair (BL , BR ) = {(sl , sr )}, where l < r, sl and sr are incompatible, and sl , sr BL BR . Apparently, SNPPair (BL , BR ) is a subset of SNPPair (IL , IR ). The incompatible SNP pairs in SNPPair (BL , BR ) determine the minimum number of the breakpoints on the boundary of BL and BR , as well as the corresponding set of haplotypes having these breakpoints. Given an interval pair, several candidate block pairs may be derived, each of which corresponds to a different SNPPair (BL , BR ). Fig. 2(a)-2(d) show four different candidate block pairs derived from the same interval pair. The exact set of incompatible SNP pairs in SNPPair (BL , BR ) depends on the positions of BL and BR , i.e., the leftmost SNP of BL , and the rightmost SNP of BR . Formally, we define the start range Rs , the end range Re of a block pair (BL , BR ) as the ranges where SNPPair (BL , BR ) remains unchanged if the leftmost SNP of BL changes within Rs and the rightmost SNP of BR changes within Re . Moreover, the breakpoint range Rb of (BL , BR ) is defined as the range where the boundary of BL and BR falls into. The breakpoint range is the overlapping region of IL and IR (if IL and IR overlap), or the boundary of IL and IR (if IL and IR are adjacent to each other). For example, in Fig. 2(a), SNPPair (BL , BR ) contains only one incompatible SNP pair (sq , sr ). The start range Rs (BL , BR ) is (sp , sq ], the end range Re (BL , BR ) is [sr , ss ), and the breakpoint range Rb (BL , BR ) is IL IR . In Fig. 2(b), SNPPair (BL , BR ) contains two incompatible SNP pairs (sq , sr ) and (sp , sr ). The start range Rs (BL , BR ) is [s , sp ] (s denotes the leftmost SNP of interval IL ), and the end range Re (BL , BR ) is [sr , ss ), and the breakpoint range Rb (BL , BR ) is IL IR . Any contained block pair (BL , BR ) of any overlapping/adjacent maximal interval pair (IL , IR ) can be a possible neighboring block pair inside a mosaic M . A subset of these block pairs constitute a mosaic. Specifically, for any neighboring block pair (BL , BR ) which is inside a Minimum Mosaic Mmin , we have the following Lemma: Lemma 4.2. Let (BL , BR ) be a neighboring block pair in a Minimum Mosaic Mmin , and B reak points(BL , BR ) be the set of breakpoints on the boundary of BL and BR in Mmin , and H apS et(B reak points(BL , BR )) be the set of haplotypes having breakpoints in B reak points(BL , BR ). Then B reak points(BL , BR ) is the smal lest number of breakpoints which satisfies: (sl , sr ) S N P P air (BL , BR ) (gl,r {00, 01, 10, 11}, H apS et(B r eak points(BL , BR )) H apS etl,lrr ) g, (1) Pro of. Details of the proof are presented in ? . It is easy to compute B reak points(BL , BR ) if SNPPair (BL , BR ) only contains one pair of incompatible SNPs (as shown in Fig. 2(a)). We can r r r r choose the smallest set of H apS etl,0 , H apS etl,1 , H apS etl,0 and H apS etl,1 1 1 0 0 to be B reak points(BL , BR ). If SNPPair (BL , BR ) contains more than one pair of incompatible SNPs (as shown in Fig. 2(b), 2(c), and 2(d)), we need to find the smallest set of haplotypes which is a superset of at least r r lr r one of H apS etl,0 , H apS etl,1 , H apS et1,0 and H apS etl,1 , for each pair of 0 0 1 incompatible SNPs (sl , sr ). The computation complexity is O(4k ), where k = |B reak points(BL , BR )|. In practice, k is small. Moreover, many incompatible SNP pairs are caused by a small number of SNP patterns, which enables further reduction in computation. 5. Finding Minimum Mosaic - A Graph Problem The set of all possible block pairs {(BL , BR )} of all overlapping/adjacent maximal interval pairs are the building blocks of a mosaic. We can use them and construct a graph as follows. A node nd in this graph represents the Haplotypes Haplotypes sp IL sq IR sr ss sp IL sq IR sr ss BL SNPs BR BL SNPs BR (a) (b) Haplotypes sp sr ss Haplotypes IL sq IR sp IL sq IR sr ss BL SNPs BR BL SNPs BR (c) (d) Figure 2. Neighb oring blocks BL , BR contain different subsets of the incompatible SNP pairs. The dots represent the incompatible SNP pairs contained in the overlapping maximal intervals IL and IR . The dots inside the shaded triangle are contained in the neighb oring block pair BL and BR . combination of three block pairs B P1 = (BL1 , BR1 ), B P2 = (BL2 , BR2 ), B P3 = (BL3 , BR3 ) that satisfy the following constraints: 1) the breakpoint range of B P1 overlaps with the start range of B P2 : Rb (B P1 )Rs (B P2 ) = ; 2) the end range of B P1 , the breakpoint range of B P2 , and the start range of B P3 overlap: Re (B P1 ) Rb (B P2 ) Rs (B P3 ) = ; 3) the end range of B P2 overlaps with the breakpoint range of B P3 : Re (B P2 ) Rb (B P3 ) = . As shown in Fig. 3, B P1 , B P2 , and B P3 are the left block pair, middle block pair, and right block pair of nd, respectively. The breakpoint range of nd is the intersection of the end range of B P1 , the breakpoint range of B P2 , and the start range of B P3 : Rb (nd) = Re (B P1 ) Rb (B P2 ) Rs (B P3 ). The set of breakpoints associated with nd is the same as B reak points(B P2 ), denoted as B reak points(nd). The weight of the node is the number of breakpoints in B reak points(nd), weig ht(nd) = |B reak points(nd)|. We also create two special kinds of nodes ­ starting nodes and ending nodes to model the two ends of a chromosome. We first identify all Block Pair 1 start BL1 breakpoint BR1 end Block Pair 2 start BL2 breakpoint BR2 end Block Pair 3 start BL3 BR3 breakpoint end node breakpoint Figure 3. Three block pairs form a node. Block pair 1, 2, and 3 are the left, middle, and right block pair of the node resp ectively. The breakp oint range of the node is the intersection of the end range of block pair 1, the breakp oint range of block pair 2, and the start range of block pair 3. The vertical strip es corresp ond to the start range, breakp oint range, and end range of a block. The marked haplotyp es in the strip es are the haplotyp es which have breakp oints in the corresp onding region. block pairs with start range beginning from the first SNP s1 , referred to as starting block pairs. We create a starting node nds for every combination of a starting block pair B Ps and another block pair B P satisfying 1) the breakpoint range of B Ps overlaps with the start range of B P : Rb (B Ps ) Rs (B P ) = , and 2) the end range of B Ps overlaps with the breakpoint range of B P : Re (B Ps ) Rb (B P ) = . B Ps is the middle block pair of the starting node nds , B P is the right block pair of nds . There is no left block pair for nds . The set of breakpoints associated with nds is the same as B reak points(B Ps ): B reak points(nds ) = B reak points(B Ps ). The weight of nds is weig ht(nds ) = |B reak points(nds )|. Similarly, we create a set of ending nodes {nde } associated with the set of ending block pairs {B Pe }. After generating all nodes, we connect nodes with directed edges according to the following rule. For nodes nd1 and nd2 , if nd1 's middle block pair is the same as nd2 's left block pair and nd1 's right block pair is the same as nd2 's middle block pair, we add an edge from nd1 to nd2 . The nodes and edges form a directed graph. A Minimum Mosaic corresponds to a shortest path from any starting node to any ending node in this graph. The weight of the path is the sum of all node weights on the path. The set of breakpoints {B reak points(nd)} associated with all nodes on the shortest path is the Minimum Mosaic solution. We can use any shortest path algorithm to compute the solution. The details of the complete algorithm and the correctness proof are presented in ? . 6. Exp erimental Studies Our algorithm is implemented in C++ and all experiments were performed on a machine with an Intel Core2 Duo processor of 1.60GHz and 3GB RAM. 6.1. Kreitman's ADH Data The alcohol dehydrogenase (ADH) data of Kreitman? consists of 11 haplotypes over 43 polymorphic sites of the ADH locus of fruit fly, Drosophila melanogaster. The haplotypes were sampled from 5 geographically distinct populations: Washington, Florida, Africa, France, and Japan? . Our algorithm detected 7 breakpoints shown in Fig. 4(a). We can estimate the exact locations of 6 out of 7 breakpoints: H1 : (S3 , S4 ), H5 : (S3 , S4 ), H5 : (S16 , S17 ), H5 : (S35 , S36 ), H6 : (S35 , S36 ), H6 : (S36 , S37 ). For the remaining breakpoint on H1 , its location can be either (S12 , S13 ), or (S13 , S14 ), or (S14 , S15 ), or (S15 , S16 ) with equal probability. Note that 7 is the lower and upper bounds of the minimum number of recombinations, estimated by HapBound and SHRUB, respectively? . Therefore, 7 is the exact number of minimum number of recombination events for the ADH data. The corresponding ARG generated by SHRUB is shown in Fig. 4(c). The breakpoints in the ARG are illustrated in a SNP matrix in Fig. 4(b). By comparing Fig. 4(a) and 4(b), we observe that almost the same set of breakpoints are inferred by our algorithm and SHRUB. 6.2. Running Time and Scalability Analysis We tested the performance of our algorithm on two genome-wide SNP data sets from mouse. Both sets represent a combination of experimental and imputed genotypes? in two overlapping sets of laboratory inbred strains available from the Center of Genome Dynamics at the Jackson's Laboratory? . The 51-strain data set contains 51 inbred mouse strains with 7,870,134 SNPsb . The 74-strain data set contains 74 inbred mouse strains b The 51-strain data set includes Chr 1-19 and Chr X, with 51 mouse strains: X129S1.SvImJ, X129S4.SvJae, X129X1.SvJ A.J, AKR.J, BALB.cByJ, BTBR.T....tf.J, BUB.BnJ, C3H.HeJ, C57BL.6J, C57BLKS.J, C57BR.cdJ, C57L.J, C58.J, CAST.EiJ, CBA.J, CE.J, CZECHI I.EiJ, DBA.1J, DBA.2J, DDK.Pas, FVB.NJ, I.LnJ, JF1.Ms, KK.HLJ, LG.J, LP.J, MA.MyJ, MAI.Pas, MOLF.EiJ, MSM.Ms, NOD.LtJ, NON.LtJ, NZB.BlNJ, NZO.HlLtJ, NZW.LacJ, O20, PERA.EiJ, PL.J, PWD.Ph, PWK.PhJ, Qsi5, RI I IS.J, SEA.GnJ, SEG.Pas, SJL.J, SM.J, SPRET.EiJ, ST.bJ, SWR.J, and WSB.EiJ. s1 h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 s5 s 10 s 15 s 20 s 25 s 30 s 35 s 43 h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 s1 s5 s 10 s 15 s 20 s 25 s 30 s 35 s 43 0000000011000000001101110111100000000000000 0010000000000000001101110111100000000000000 0000000000000000000000000000000000010000101 0000000000000000110000000000000000010011000 0001100010110011110000000000000000001000000 0010000000000001000000000000001010111000010 0010000000000001000000000000011111101000000 1111100010111001000000000000011111101100000 1111100010111001000000000000011111101100000 1111100010111001000000000000011111101100000 1111111110000101000010001000011111101000000 0000000011000000001101110111100000000000000 0010000000000000001101110111100000000000000 0000000000000000000000000000000000010000101 0000000000000000110000000000000000010011000 0001100010110011110000000000000000001000000 0010000000000001000000000000001010111000010 0010000000000001000000000000011111101000000 1111100010111001000000000000011111101100000 1111100010111001000000000000011111101100000 1111100010111001000000000000011111101100000 1111111110000101000010001000011111101000000 (a) (b) a: (3,4) b: (3,4) d: (16,17) c: e : (15,16) (35,36) f: (35, 36) g: (36,37) H3 H4 H5 H1 H8 H9 H7 H6 H2 (c) Figure 4. Comparison of Minimum Mosaic and Hapb ound/SHRUB results on ADH data. (a): the Minimum Mosaic result; (b): the result inferred from the ARG in (c); (c): the ARG computed using SHRUB? . The bars in (a) and (b) represent the breakp oints. The dots in (c) represents the recombination events. with 7,989,200 SNPsc . Fig. 5 shows the running time comparison of Hapbound and our algorithm using the first w SNPs from Chromosome 19 of both data sets where w varies from 1000 to 4000. Our algorithm is 250x - 7000x faster than Hapbound on 74-strain dataset, and 350x - 4000x faster on 51-strain dataset. Our algorithm is efficient enough to finish on all chromosomes (Chr 119 and Chr X). Results from the 51-strain data set are shown in Table 1. Genome-wide, the number of breakpoints in the Minimum Mosaic varies between 15253 (Chr X) and 266006 (Chr 1), and the number of derived blocks in the Minimum Mosaic varies between 9888 (Chr X) and 68261 c The 74-strain dataset includes all strains in the 51-strain data set and 23 additional strains: BALB.cJ, BPH.2J, BPL.1J, BPN.3J, C57BL.10J, CALB.RK, DDY.JCLSIDSEYFRKJ, EL.SUZ 2, HTG.GOSFSN, ILS, IS.CAMRK, ISS, LEWES.EI, MOLG.DN, MRL.MpJ, NOR.LTJ, P.J, PERC.EI, RF.J, SKIVE.EI, SOD1.EI, TALLYHO.JNGJ, and ZALENDE.EiJ. Log Scale Plot of Running Time (Chr19, 51 strains) Running Time (sec) 1000 100 10 1 0.1 0.01 1000 1500 2000 2500 3000 # of SNPs 3500 4000 Hapbound MinMosaic Running Time (sec) Log Scale Plot of Running Time (Chr19, 74 strains) 10000 1000 100 10 1 0.1 1000 Hapbound MinMosaic 10000 1500 2000 2500 3000 # of SNPs 3500 4000 (a) 51-strain Dataset (b) 74-strain Dataset Figure 5. Comparison of the running times of MinMosaic and Hapb ound over varying numb er of SNPs (in log scale). The datasets used are from Chr19 of 51-strain dataset and 74-strain dataset. The numb er of SNPs included varies from 1000 to 4000. (Chr 1). The average number of breakpoints per neighboring block pair is 2.2. Table 1. C hr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 X The result on genome-wide 51-strain mouse data set. # of breakp oints 266006 210797 113715 100702 110157 97740 94973 87659 86755 64806 65092 89243 75323 67304 78181 57257 73542 69546 49276 15253 # of blocks 68261 47793 52487 43776 49938 49562 46884 45796 40189 35764 27575 42159 39914 34089 35776 28449 31517 31271 22839 9888 Runtime (min) 6.87 11.27 8.90 7.84 33.98 6.42 38.83 37.10 3.89 3.21 23.52 1.30 3.03 2.54 4.08 1.14 0.75 8.61 1.46 0.96 # of SNP 694809 524667 509892 476425 496888 509547 405733 444910 361571 399126 259028 396114 399930 345783 337461 305078 266421 291266 222031 223456 7. Conclusions Genetic recombination during meiosis generates a mosaic structure of the genome, where each resulting haplotype consists of segments from different ancestral sequences. In this paper, we study the Minimum Mosaic model that contains a minimum number of breakpoints to generate the haplotypes present within extant populations. The resulting blocks are compatible where no recombinations can be inferred within a block according to the FGT. We proposed a novel algorithm to compute the minimum mosaic structure of genomes. the efficiency of our algorithm allows for genomewide analysis. References 1. Gusfield,D. (2005) Optimal, efficient reconstruction of ro ot-unknown phylogenetic networks with constrained and structured recombination, Journal of Computer and System Sciences, 70, 381-398. 2. Hudson,R., Kaplan,N. (1985) Statistical prop erties of the numb er of the recombination events in the history of a sample of DNA sequences, Genetics, 111, 147-164. 3. Kreitman,M. (1983) Nucleotide p olymorphism at the alcohol dehydrogenase lo cus of Drosophila melanogaster, Nature, 304, 412-417. 4. Mo ore,K., Zhang,Q, McMillan,L., Wang,W., Pardo-Manuel de Villena,F. (2008) Genome-wide compatible SNP intervals and their prop erties, UNC Tech Rep ort, June 08. 5. Myers,S.R., Griffiths,R.C. (2003) Bounds on the minimum numb er of recombination events in a sample history, Genetics, 163, 375-394. 6. Schwartz,R., Halldorson,B.V., Bafna,V., Clark,A.G., Istrail,S. (2003) Robustness of inference of haplotyp blo ck structure, J. Comput. Biol., 10, 13-19. 7. Song,Y.S., Wu,Y, Gusfield,D. (2005) Efficient computation of close lower and upp er b ounds on the minimum numb er of recombinations in biological sequence evolution, Bioinformatics, 21, i413-i422. 8. Song,Y.S., Hein,J. (2005) Constructing minimal ancestral recombination graphs, J. Comput. Biol., 12(2), 147-169. 9. Song,Y.S., Hein,J. (2003) Parisimonious reconstruction of sequence evolution and haplotyp e blo cks: finding the minimum numb er of recombination events, Proceedings of the Third International Workshop on Algorithms in Bioinfomatics (WABI 2003), 287-302. 10. Szatkiewicz,J.P., Beane,G.L., Ding,Y., Hutchins,L., Pardo-Manuel de Villena,F., Churchill,G. (2008) An imputed genotyp e resource for the lab oratory mouse, Mamm Genome, 19:199. 11. Ukkonen, E. (2002) Finding founder sequences from a set of recombinants, WABI 2002, 277-286. 12. Wang,L., Zhang,K., Zhang,L. (2001) Perfect phylogenetic networks with recombinaiton, J. Comput. Biol., 8, 69-78. 13. Wu, Y., Gusfield, D. (2007) Improved algorithms for inferring the minimum mosaic of a set of recombinants, CPM 2007, 150-161. 14. Zhang,K., Deng,M., Chen,T., Waterman,M.S., Sun,F. (2003) A Dynamic programming algorithm for haplotyp e blo ck partitioning, PNAS., 99, 73357339. 15. Zhang, Q., Wang, W., McMillan, L., Villena, F.P., Threadgill, D. (2008) Inferring genome-wide mosaic structure, UNC Tech. Rep ort (2008). 16. http://cgd.jax.org/ImputedSNPData/imputedSNPs.htm.