{'fraction_non_alphanumeric': 0.036749513550380135, 'fraction_numerical': 0.023670538203847465, 'mean_word_length': 5.057351154313487, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 11, 'https://': 5, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The genomic history of the Middle East

Summary The Middle East region is important to understand human evolution and migrations but is underrepresented in genomic studies. Here, we generated 137 high-coverage physically phased genome sequences from eight Middle Eastern populations using linked-read sequencing. We found no genetic traces of early expansions out-of-Africa in present-day populations but found Arabians have elevated Basal Eurasian ancestry that dilutes their Neanderthal ancestry. Population sizes within the region started diverging 15–20 kya, when Levantines expanded while Arabians maintained smaller populations that derived ancestry from local hunter-gatherers. Arabians suffered a population bottleneck around the aridification of Arabia 6 kya, while Levantines had a distinct bottleneck overlapping the 4.2 kya aridification event. We found an association between movement and admixture of populations in the region and the spread of Semitic languages. Finally, we identify variants that show evidence of selection, including polygenic selection. Our results provide detailed insights into the genomic and selective histories of the Middle East.

In brief A high-coverage resource of physically phased genomes from eight Middle Eastern populations generated via linkedread sequencing provides insights into a genetically understudied region and enables more comprehensive study of population history and the detection of millions of variants common to the Middle East but outside short-read accessibility masks and not previously cataloged. It enhances our understanding of regional ancestry, the spread of languages, the effects of climate change on populations, and the evolutionary history of genetic variants.

INTRODUCTION
Global whole-genome sequencing projects have provided insights into human diversity, dispersals, and past admixture events (Bergströ m et al., 2020;Mallick et al., 2016;GenomeA-sia100K Consortium, 2019;1000Genomes Project Consortium et al., 2015. However, many populations remain understudied, which restricts our understanding of genetic variation and population history and may exacerbate health inequalities (Sirugo et al., 2019). A region particularly understudied by large-scale sequencing projects is the Middle East (Fernandes et al., 2019;Abou Tayoun and Rehm, 2020). Situated between Africa, Europe, and South Asia, it forms an important region to understand human evolution, history, and migrations. The region contains some of the earliest evidence of modern humans outside Africa, with fossils dated to at least 177 thousand years ago (kya) and $85 kya identified in the Levant and North West Arabia, respectively (Hershkovitz et al., 2018;Groucutt et al., 2018). In addition, tools and footprints attributed to modern humans have also been identified in Arabia $120 kya (Armitage et al., 2011;Stewart et al., 2020). Although most of Arabia is a hyper-arid desert today, there were several humid periods resulting in a ''green Arabia'' in the past which facilitated human dispersals, with the onset of the current desert climate thought to have started around 6 kya (Petraglia et al., 2020). The toggling from humid to arid periods in the late Pleistocene and Holocene has been proposed to result in population movements adapting to the climate. The Neolithic transition within Arabia may have developed independently within the region or resulted from an expansion of Levantine Neolithic farmers southward (Drechsler, 2009;Uerpmann et al., 2010;Crassard andDrechsler, 2013a, 2013b;Hilbert et al., 2015). To address such questions, we generated and analyzed a high-coverage physically phased dataset of populations from the Arabian Peninsula, the Levant, and Iraq. In addition to creating a catalog of genetic variation in an understudied region that will assist future medical studies, we have investigated the population structure, demographic and selective histories, and admixture events with modern and archaic humans.

Dataset and sample sequencing
We sequenced 137 whole genomes from eight Middle Eastern populations (Figure 1A) to an average coverage of 323 using a library preparation method that preserves long-range information from short reads and aligned them to the GRCh38 reference (STAR Methods). An advantage of using this ''linked-read'' technology is the reconstruction of physically phased haplotypes and improved alignments at repetitive regions that confound shortread aligners. All populations investigated speak Arabic, a Semitic language of the Afro-Asiatic language family, with the exception of the Iraqi Kurdish group who speak Kurdish, an Iranian language belonging to the Indo-European family. After quality control (STAR Methods), we identified 23.1 million singlenucleotide variants (SNVs). We compared our dataset to variants identified in the recently released Human Genome Diversity Project (HGDP-CEPH) study (Bergströ m et al., 2020). We found 4.8 million autosomal SNVs in our dataset that are not found in the HGDP. As expected, most of the these variants are rare (93%, <1% minor allele frequency); however, $370,000 are common (>1%). Interestingly, most of these common variants are outside the accessibility mask defined by Bergströ m et al., 2020 ($246,000 variants in $27% of the genome). This illustrates the importance of sequencing genetically under-represented populations such as Middle Easterners and the inclusion of regional-private variants in future medical studies. It also demonstrates that a significant amount of unknown variation resides in regions that are not accessible to standard short-reads.
Population structure and admixture Uncovering population structure and past admixture events is important for understanding population history and for designing and interpreting medical studies. We explored the structure and diversity of our dataset using both single-variant and haplotypebased methods. After merging our dataset with global populations, fineSTRUCTURE  identified genetic clusters that are concordant with geography and showed that self-labeled populations generally formed distinct clusters (Figure 1C). Populations from the Levant and Iraq (Lebanese, Syrians, Jordanians, Druze, BedouinA, and Iraqi-Arabs) clustered Eigenvectors were inferred with present-day populations from the Middle East, Europe, and Central and South Asia. The ancient samples were then projected onto the plot (all modern non-Middle Easterners shown as gray points). See Figure S1 for more details. (E) Genetic contrast between the Levant and Arabia illustrated using the statistic f4(Syrian,EmiratiA;Ancient,Chimpanzee) and ± 3 standard errors with the 10 lowest (blue) and 10 highest (red) f4-stats. together, while Iraqi-Kurds clustered with Central Iranian populations. Arabian populations (EmiratiA, Saudis, Yemenis, and Omanis) clustered with BedouinB from the HGDP. Within the Emirati population, we identified subpopulations with excess Iranian and South Asian ancestries (EmiratiB and EmiratiC;Figure 1B). We also found subpopulations harboring relatively higher African ancestry (SaudiB, EmiratiD; Figure 1B).
We next analyzed our samples in the context of ancient regional and global populations. Principal component analysis ( Figures 1D and S1) shows that present-day Middle Easterners are positioned between ancient Levantine hunter-gatherers (Natufians), Neolithic Levantines (Levant_N), Bronze Age Europeans, and ancient Iranians. Arabians and Bedouins are positioned close to ancient Levantines, while present-day Levantines are drawn toward Bronze Age Europeans. Iraqi-Arabs, Iraqi-Kurds, and Assyrians appear relatively closer to ancient Iranians. We found that most present-day Middle Easterners can be modeled as deriving their ancestry from four ancient populations (Table 1): Levant_N, Neolithic Iranians (GanjDareh_N), Eastern Hunter Gatherers (EHG), and an $4,500-year-old East African (Mota). We observed a contrast between the Levant and Arabia: Levantines have excess EHG ancestry ( Figure 1E), which we showed previously had arrived in the Levant after the Bronze Age along with people carrying ancient south-east European and Anatolian ancestry (Haber et al., 2017. Our results here show this ancestry is much higher in the Levant compared to Arabia (Table 1). Another contrast between the Levant and Arabia is the excess of African ancestry in Arabian populations. We found that the closest source of African ancestry for most populations in our dataset is Bantu Speakers from Kenya, in addition to contributions from Nilo-Saharan speakers from Ethiopia. We estimate that African admixture in the Middle East occurred within the last 2,000 years, with most populations showing signals of admixture around 500-1,000 years ago ( Figure S1; Table S1), in agreement with previous studies (Hellenthal et al., 2014).
In addition to differences in EHG and African ancestries, we observed an excess of Natufian ancestry in Arabia compared with the Levant (Figures 1B and 1E). When we substituted Le-vant_N with Natufians as source of ancestry in the Middle East, we found that Arabians could be successfully modeled (Table 1), whereas none of the present-day Levantines could be modeled as such. Model-based clustering also showed that Arabian populations have substantially lower Anatolia Neolithic (Anatolia_N) ancestry compared with modern-day Levantines (purple component in Figure 1B). The differences in ancient Anatolian ancestry could be from a limited Levant_N expansion into Arabia, as Levant_N shares significant ancestry with Anato-lia_N , but could also be from post-Bronze Age events with the expansion of populations carrying Anato-lia_N ancestry into the Levant .
In addition to the local ancestry from Epipaleolithic/Neolithic people, we found an ancestry related to ancient Iranians that is ubiquitous today in all Middle Easterners (orange component in Figure 1B; Table 1). Previous studies showed that this ancestry was not present in the Levant during the Neolithic period but appeared in the Bronze Age where $50% of the local ancestry was replaced by a population carrying ancient Iran-related ancestry . We explored whether this ancestry penetrated both the Levant and Arabia at the same time and found that admixture dates mostly followed a North to South cline, with the oldest admixture occurring in the Levant region between 3,300 and 5,900 ya (Table S2), followed by admixture in Arabia (2,000-3,500 ya) and East Africa (2,100-3,300 ya). These times overlap with the dates for the Bronze Age origin and spread of Semitic languages in the Middle East and East Africa estimated from lexical data (Kitchen et al., 2009;Figure 2). This population potentially introduced the Y chromosome haplogroup J1 into the region (Chiaroni et al., 2010;Lazaridis et al., 2016). The majority of the J1 haplogroup chromosomes in our dataset coalesce around $5.6 (95% CI, 4.8-6.5) kya, agreeing with a potential Bronze Age expansion; however, we did find rarer earlier diverged lineages coalescing $17 kya ( Figure S2). The haplogroup common in Natufians, E1b1b, is also frequent in our dataset, with most lineages coalescing $8.3 (7-9.7) kya, though we also found a rare deeply divergent Y chromosome, which coalesces 39 kya ( Figure S2).
We next tested whether we can model our populations as deriving ancestry from one of the sampled regional Bronze Age populations and found that the Middle Bronze Age population from Sidon (Sidon_BA) could be a source of ancestry for some modern Levantine and Arabian populations (Tables S3 and S4). Our phylogenetic modeling suggests that modern Levantines could have directly derived their ancestry from a Sidon_BArelated population; however, Arabians require additional ancestry from a Natufian-related population (Figures 3 and S3).

Effective population size and separation history
Historical effective population sizes can be inferred through the distribution of coalescence times between chromosomes sampled from a population (Li and Durbin, 2011). However, there is limited resolution in recent periods using single human genomes, while errors in haplotype phasing create artifacts when using multiple genomes (Schiffels and Durbin, 2014;Terhorst et al., 2017). Although methods have been developed that extend these approaches by incorporating the allele frequency spectrum from unphased genomes, they do not have resolution at recent times, for example, through the metal ages (Terhorst et al., 2017;Bergströ m et al., 2020). By leveraging recent advances in generating genome-wide genealogies , and the large number of physically phased samples in our study, we could estimate the effective population size of each population in our dataset up to very recent times-1 kya ( Figures 4A and S4). We found that the ancestors of all Middle Easterners show a significant decrease in population size around the out-of-Africa event $50-70 kya. The recovery from this bottleneck follows a similar pattern until 15-20 kya, when a contrast between the Levant and Arabia started to emerge. All Levantine and Iraqi populations continued to show a substantial population expansion, while Arabians maintained similar sizes. This contrast is noteworthy since it starts after the end of the Last Glacial Maximum and becomes prominent during the Neolithic, when agriculture developed in the Fertile Crescent and led to settled societies supporting larger populations. Following the Neolithic, and with the start of the aridification of Arabia around 6 kya, Arabian populations experienced a ll OPEN ACCESS The choice of a 4-way admixture derives from previous knowledge on the region with Levant_N and GanjDareh_N contributing significant ancestry to ancient Near Easterners , EHG/Steppe ancestry penetrating the region after Bronze Age (Haber et al., 2017, and African ancestry (represented by Mota; Gallego Llorente et al., 2015) found today in most Levantines and Arabians (Moorjani et al., 2011;Haber et al., 2013). We used seven outgroups in the test: Ust'-Ishim, Kostenki14, WHG, CHG, Natufian (or Levant_N), Papuan, and Mbuti. Standard error range for Levant_N (0.02-0.03); Iran_N (0.02-0.03); EHG (0.01-0.02); Mota (0.005-0.01); Natufian (0.02). a p > 0.05 indicates the model is not rejected. .HO, samples from the Human Origins dataset. We note here that these ancient populations represent proxies to the actual populations that contributed to the ancestors of modern populations.
bottleneck while Levantines continued to increase in size. The expansion in Levantines then plateaus and their population size decreases around the 4.2 kiloyear aridification event (Weiss et al., 1993). The decline in Emiratis is especially prominent, reaching an effective population size of $5,000, more than 20 times smaller than Levantines and Iraqis at the same time period. A recovery can be observed in the past 2 ky. Our results are robust to recent consanguinity common in the region that has likely affected previous population size estimates (Bergströ m et al., 2020), as we included a single haplotype per sample in our analysis ( Figure S4). We next studied the population separation history of Middle Eastern populations among themselves and from global populations. The importance of accurate phasing in this analysis is illustrated by an earlier finding that suggested, based on statistically phased data, that modern-day Papuans harbor ancestry of an early expansion of modern humans out of Africa . However, this was not replicated using physically phased genomes, suggesting it was caused by a statistical phasing artifact (Bergströ m et al., 2020). Conversely, when exploring population separation history at recent times, rare variants become more informative but are less accurately phased by statistical methods and are unlikely to be present in reference panels. We first tested whether present-day Middle Easterners harbor ancestry from an early human expansion out of Africa by comparing the split times of our populations with physically phased samples from the HGDP (Figures 4B and S5). Using a relative cross-coalescent rate (rCCR) of 0.5 as a heuristic estimate of split time, we found that Levantines, Arabians, Sardinians, and Han Chinese share the same split time, and additionally the same gradual pattern of separation, from Mbuti $120 kya. We then compared the populations in our dataset with Sardinians and found they split $20 kya, with Levantines showing a slightly more recent divergence than Arabians. In contrast to the gradual separation patterns to Mbuti, Sardinians show more of a clean split to all Middle Eastern populations. Notably, all lineages within the Levant and Arabia, and in addition to lineages within all Middle Eastern populations and Sardinians, coalesce within 40 kya. These results collectively suggest that present-day Middle Eastern populations do not harbor any significant traces from an earlier expansion out of Africa, and all descend from the same population that expanded out of the continent $50-60 kya.
We then compared the separation times of populations within the Middle East and found the oldest divergence times were between Arabia and the Levant/Iraq ( Figures 4C and S4). The Emiratis split from Iraqi-Kurds around 10 kya, and more recently around 7 kya from Jordanians, Syrians, and Iraqi-Arabs. Saudi split times from the same populations appear more recent, around 5-7 kya, while the Yemeni separation curves are intermediate between the Emirati and Saudi curves. The split times between Arabia and the Levant predate the Bronze Age, agreeing with our phylogenetic modeling that, if a Bronze Age expansion into Arabia occurred, it did not result in a complete replacement of ancestry.
Within the Levant and Iraq, all splits occurred in the past 3-4 ky. Within Arabia, Yemenis split from Emiratis $4 kya and Saudis appear as the least divergent population to both the Emiratis and Yemenis, with recent splits within the last 2 ky. We note that the separation curves within the region appear gradual, suggesting ongoing gene flow after separation rather than clean splits. We also note that the separation curves will reflect the admixture histories of these populations.

Archaic introgression and deep ancestry in the Middle East
The similar amount of Neanderthal ancestry in most non-African populations and the low diversity of introgressed haplotypes suggest that modern humans likely experienced a single pulse of Neanderthal admixture as they expanded out of Africa (Bergströ m et al., 2020). Middle Eastern populations have previously been shown to have lower Neanderthal ancestry than European and East Asian populations (Rodriguez-Flores et al., 2016;Bergströ m et al., 2020); however, the interpretation of this finding is complicated by recent African admixture ''diluting'' Neanderthal ancestry (Haber et al., 2016). In addition, some analyses require the use of an outgroup, which, if itself contains Neanderthal ancestry, can bias estimates (Chen et al., 2020). To investigate Neanderthal introgression in our dataset, we exploited the  . They proposed that the current distribution of Ethiosemitic languages reflect a language diffusion process through African populations, rather than gene flow. Our admixture tests Tables S3 and S4 also suggest an ancient Egyptian source of ancestry in East Africa, rather than from Arabia, although ancient DNA from Arabia is still missing to make a comparable analysis. See also Figure  We then used an identity-by-descent-based method, IBDmix, which directly compares a target population to the Neanderthal genome to detect haplotypes of Neanderthal origin (Chen et al., 2020). We ran IBDmix on our samples and the HGDP dataset, recovering segments totaling $1.27 Gb that are of likely Neanderthal origin. When comparing the amount of Neanderthal haplotypes that are private to our dataset but not present in other non-Middle Eastern Eurasians, we found only $25 Mb in total, illustrating that the vast majority of Neanderthal haplotypes in the region are shared with other populations. However, we did find relatively large introgressed haplotypes ($500 kb) that are very rare globally but reach high frequencies in Arabia ( Figure S6). We then compared the average number of total Neanderthal bases per population and found lower values in Arabia in comparison to other Eurasian populations, including Levantines. The Druze and Sardinians, for example, have similar amounts (average $56.4 Mb per individual) of Neanderthal ancestry (Figure 5B). In contrast, in Arabia, EmiratiA and SaudiA have an average of 52.7 and 52.1 Mb Neanderthal ancestry, respectively, which is $8% lower than the Druze and Sardinians, and $20% less than Han Chinese. Since EmiratiA and SaudiA have less than 3% of African ancestry (Table 1), the depletion of Neanderthal ancestry in Arabia cannot be explained by the African ancestry alone. Lazaridis et al., (2016) proposed that a basal Eurasian population, with low-to-no Neanderthal ancestry, had contributed different proportions to ancient and modern Eurasians, reaching $50% in Neolithic Iranians and Natufians. Since Arabians have an excess of Natufian-like ancestry compared to elsewhere in the Middle East, we found they also carry an excess of basal Eurasian ancestry that will reduce their Neanderthal ancestry. In addition, most modern Middle Easterners carry African ancestry from recent admixture, which also contributes to their deep ancestry (relative to the time of a main Eurasian ancestry). We found a negative correlation (Pearson's r = À0.7, p = 9.1 3 10 À6 ) between the increase in deep ancestry and the amount of Neanderthal ancestry in the modern Middle Easterners. When testing all ancient populations, we found two clines ( Figure 5C) explaining the depletion of Neanderthal ancestry: the first is formed by African ancestry while the second is formed by a Basal Eurasian ancestry in ancient Eurasians. Middle Easterners appear to be affected by both clines since they harbor both ancestries.

Selection
The current hyper-arid climate may have potentially exerted selective pressure for adaptations in Arabian populations. To explore this, we searched genome-wide genealogies for Populations in ellipses are sampled populations, while populations in boxes are hypothetical. Worst f-statistics: Z score = À2.9. We explore models further in Figure S3. BA, Bronze Age; HG, hunter-gatherer.
lineages carrying mutations that have spread unusually quickly  at a conservative genome-wide threshold (p < 5 3 10 À8 ). Previous studies identified two correlated variants (rs41380347 and rs55660827), distinct from the known European variant (rs4988235), that are associated with lactase persistence in Arabia (Imtiaz et al., 2007;Enattah et al., 2008). For the Arabian variant rs41380347, we found evidence for strong selection (Figure 6A, s = 0.011, logLR = 13.3), similar to, but slightly weaker than, the reported strength of selection at rs4988235 in Europeans (s = 0.016-0.018; Stern et al., 2019). The variant is present at highest frequency in the Arabian populations: $50% in Saudis and Emiratis, and at a much lower frequency in the Levant and Iraq (4%). Remarkably, the variant is not present in any Eurasian or African population in the 1000 Genomes Project (1KG), although it is found at low frequency in some East African groups (Tishkoff et al., 2007). We also did not find the variant in 157 published ancient Eurasian whole genomes (Broushaki et al., 2016;de Barros Damgaard et al., 2018;Haber et al., 2017Haber et al., , 2019aHaber et al., , 2020Jones et al., 2015), including ancient Levantines and Iranians, consistent with a recent origin of the haplotype within the Middle East and subsequent increase in frequency due to selection. We found the variant had a rapid increase in frequency between 9 kya and the present day ( Figure 6A). Notably, this period overlaps with the transition from a hunter-gatherer to a herder-gatherer lifestyle in Arabia (Petraglia et al., 2020).
We also identified additional variants that show an increase in frequency recently. A variant within LMTK2, rs11762534, which is also an eQTL for many genes, displays evidence of putative selection ( Figure 6B, s = 0.005; logLR = 16.5). LMTK2 encodes a serine/threonine kinase that is implicated in diverse cellular processes including apoptosis, growth factor signaling and appears essential for spermatogenesis in mice (Cruz et al., 2019;Kawa et al., 2006). Outside the Middle East the variant is highly stratified and is present at the highest frequency in Europeans (1KG, 45%), while rare in Africans and East Asians (<1%). We found it at 66% frequency in the Arabian populations and in BedouinB (81%), while appearing less frequent in Druze and Palestinians (both $55%). We also found a signal of strong putative selection at rs35241117 ( Figure 6C, s = 0.007, logLR = 8.1). This variant shows the highest global frequency in Saudis and Yemenis ($60%) and is associated with a number of metabolic, skeletal, and immunological traits, including glomerular filtration rate, diuretics, hypertension, and BMI (Watanabe et al., 2019;Canela-Xandri et al., 2018). rs35241117 lies outside a $400 kb haplotype that has recently been suggested to be under selection in Kuwaitis and Saudis (Eaaswarkhanth et al., 2020) but is in moderate LD (r 2 = 0.51) with it.
We additionally looked for strongly differentiated variants between Arabia and the Levant/Iraq ( Figure S7). For both Emiratis and Saudis, we found a strong signal of differentiation at a 97kb haplotype on chromosome 7 ( Figure S7). Variants on this haplotype (rs1734235) almost reach fixation in Arabians and are associated with increased expression of the lincRNA AC003088.1 in cultured fibroblasts (GTEx Analysis Release V8; Horizontal lines depict 25%, 50%, and 75% quantiles. Colors reflect regional grouping. (C) Neanderthal ancestry f4(Vindija,Chimp;X,Mbuti) is negatively correlated with a deep ancestry f4(Kostenki14,X;Ust '-Ishim,Chimp) in the Middle East. Two clines explain the depletion of Neanderthal Ancestry in Middle Easterners; one formed by Basal Eurasian ancestry and the other is African ancestry. We plot regression lines using East Africans (red) and the ancient Eurasians (blue). We generated standard errors for the slopes using a jackknife by dropping one chromosome. Ancient Eurasian slope m = À0.21 ± 0.002, East African slope m = À0.06 ± 0.0008. Both slopes are always negative. See also Figure S6.
The GTEx Consortium, 2020). The most extreme population branch statistic in Yemenis is rs2814778 (Figure S7), where the derived allele results in the Duffy null phenotype and is almost exclusively found in African populations in the 1000 Genomes Project. However, the variant is very common in Yemenis (74%), and decreases in frequency moving northward in the peninsula (59% in Saudis while reaching 6% in Iraqi-Arabs). We found that across the genome this region shows the highest enrichment of African ancestry in the Middle East, in agreement with a previous study (Fernandes et al., 2019). As the average amount of African ancestry in Yemenis and Saudis is $9% and $3% respectively (Table 1), the high frequency of this variant appears consistent with positive selection after African admixture. It has been thought that the derived allele protects against Plasmodium vivax infection (Miller et al., 1976), which has been historically present in Arabia.
An advantage of using genome-wide genealogies is its power to detect relatively weak selection. We subsequently searched for evidence of polygenic adaptation in Arabian populations across 20 polygenic traits specifically over the past 2,000 years (STAR Methods). For most traits, we found no, or inconclusive, evidence for recent directional selection, including height, skin color, and BMI ( Figure 6D). However, a few traits do show evidence, with the strongest putative selection signal appearing on genetic variants associated with higher years of education in present-day Western societies (EduYears) consistent across all Arabian populations (p = 0.0002 in Saudis). This has also been reported in the British population (Stern et al., 2021); however, the signal was shown to become attenuated after conditioning on other traits, suggesting indirect selection via a correlated trait. In contrast to findings in the British population (Stern et al., 2021), we do not find evidence of putative selection acting on traits such as sunburn, hair color, and tanning ability. Within Arabia, the direction of putative selection on most traits appears to be similar across populations, likely as a result of shared ancestry; however, we note that the current varied environments across the region can potentially cause different recent selective pressures. In Emiratis, we found evidence of putative selection (C) Frequency trajectory of rs35241117, which is present at the highest frequency in Arabia globally and is associated with multiple traits including glomerular filtration rate, bone mineral density, BMI, standing height, and hypertension. (D) Testing for recent polygenic selection, over the past 2,000 years, on 20 traits within Arabian populations. Asterisks indicate the test is significant after correcting for multiple testing (FDR = 5%). TRIGL, triglycerides; T2D, type 2 diabetes; SYS, systemic blood pressure; LDL, low-density lipoproteins; HTN, hypertension; HIP_CIRC, hip circumference; HDL, high-density lipoproteins; GLYC_H, glycosylated haemoglobin; FVC, forced vital capacity; EDU_YEARS, years of education; DIAS, diastolic blood pressure; BMI, body mass index; BMD, bone mass density; APOB, Apoliprotein B. See also Figure S7. ll OPEN ACCESS on variants increasing type 2 diabetes (T2D, p = 0.004). This result is intriguing, as the prevalence of T2D in Emiratis is among the highest globally and is partly thought to result from strong recent shift to a sedentary lifestyle (Malik et al., 2005). We also found nominal evidence of putative selection acting to increase levels of low-density lipoproteins (LDL; p = 0.01) and decrease levels of Apoliprotein B (APOB; p = 0.01) in the same population, but, they appear suggestive after adjusting for multiple testing (P adj = 0.06 at 5% FDR).

DISCUSSION
In this study, we have generated a high-coverage resource from the genetically understudied Middle East region. All samples studied are experimentally phased using linked-read sequencing, allowing the reconstruction of large and accurate haplotypes. We found millions of variants that are not cataloged in previous global sequencing projects, with a significant proportion being common in the Middle East. A majority of these common variants reside outside of short-read accessibility masks, highlighting the limitation of standard short-read sequencing based studies.
The large number of physically phased haplotypes allowed us to study population history from relatively old periods (>100 kya) to very recent times (1 kya). We found no evidence that an early expansion of humans out of Africa has contributed genetically to present-day populations in the region. This finding adds to the growing consensus that all contemporary non-African modern humans descend from a single expansion out-of-Africa, quickly followed by admixture with Neanderthals, before populating the rest of the world Bergströ m et al., 2020). We found that Middle Eastern populations have very little Neanderthal DNA that is private to the region, with the vast majority shared with other Eurasians. We demonstrated that Arabian populations have lower Neanderthal ancestry than Levantine, European, and East Asian populations and attributed this difference to elevated ancestry from a basal Eurasian population, which did not admix with Neanderthals, in addition to recent African admixture.
By modeling contemporary populations using ancient genomes, we identified differences between the Levant and Arabia. The Levant today has higher European/Anatolian-related ancestry while Arabia has higher African and Natufian-like ancestries. The contrast between the regions is also illustrated by their population-size histories that diverged before the Neolithic (15-20 kya) and suggest that the transition to a sedentary agricultural lifestyle allowed the growth of populations in the Levant but was not paralleled in Arabia. It has been suggested that population discontinuity occurred between the late Pleistocene and Early Holocene in Arabia and that the peninsula was repopulated by Neolithic farmers from the Fertile Crescent (Uerpmann et al., 2010). Our results do not support a complete replacement of the Arabian populations by Levantine farmers. In addition, our models suggest that Arabians could have derived their ancestry from Natufian-like local huntergatherer populations instead of Levantine Farmers. The identification of lithic assemblages in Northern Arabia, some of which appear similar to ones made by Levantine farmers (Crassard and Drechsler, 2013a), in addition to the movement of animal domesticates between the Levant and Arabia, have been suggested to occur either due to population movements or through cultural diffusion (Guagnin et al., 2017;Petraglia et al., 2020). Our results suggest the latter scenario and/or limited migration from the Levant.
An additional source of ancestry needed to model modern Middle Easterners is related to ancient Iranians. Our admixture tests show that this ancestry first reached the Levant and subsequently reached Arabia and East Africa. The timings of these events interestingly overlap with the origin and spread of the Semitic languages (Kitchen et al., 2009), suggesting a potential population carrying this ancestry (possibly unsampled yet from the Levant or Mesopotamia) may have spread the language. We found climate change associated aridification events to coincide with population bottlenecks, with Arabians decreasing in size $6 kya with the onset of the desert climate while Levantines around the 4.2 kiloyear aridification event. This severe drought has been suggested to have caused the collapse of kingdoms and empires in the Middle East and South Asia, potentially reflected genetically in the signal we identify (Weiss, 2017).
The application of ancestral recombination graphs to reconstruct the evolutionary history of variants offers a powerful method to study natural selection. We refined and identified signals of selection in Arabian populations. The example of the lactase persistence associated variant, which during the past few thousand years increased to a frequency reaching 50% and is almost absent outside the region, demonstrates the importance of studying underrepresented populations to understand human history and adaptation. Our results indicate that polygenic selection might have played a role in increasing the frequency of variants that were potentially beneficial in the past but today are associated with diseases such as T2D. We found few signals of polygenic selection in Arabian populations relative to other populations Stern et al., 2021), which may be a consequence of their long-term small effective population sizes that will theoretically reduce the strength of selection . The long-term small effective population size, especially coupled with the recent practice of consanguinity, can be exploited for the study of Mendelian and complex traits, as individuals are more likely to carry homozygous loss-of-function mutations and serve as natural ''human knockouts.'' Our study and the recent establishment of national biobanks in the region are a step forward to reduce health disparities and offer an exciting opportunity to explore, in the future, complex, and disease traits in the Middle East.
Limitations of the study Future ancient DNA studies from Arabia are needed to refine the formation of Arabian populations and to further clarify prehistorical connections between the Levant and Arabia. As Middle Eastern populations are among the most underrepresented in GWAS (Sirugo et al., 2019), this limits the understanding of selection signals and the analysis of polygenic traits. Future GWAS on Middle Eastern groups are needed to understand the effects of polygenic selection in these populations.

ACKNOWLEDGMENTS
We are grateful to Matthew Hurles, Richard Durbin, and members of the Tyler-Smith and Martin groups for constructive discussions and comments. We would particularly like to thank the participants for donating samples for this study. We thank Faisal Al-Hedeithy, Parwar Hamad, Tariq Zeyad, and Mohamed Naji for their assistance in study design. M.A.A. was supported by the Government of Dubai -Dubai Police GHQ. C.T.-S. and Y.X. were supported by Wellcome grant 098051. P.H. was supported by Estonian Research Council Grant PUT1036. Parts of the computations described in this paper were performed using the University of Birmingham's BlueBEAR HPC service.

DECLARATION OF INTERESTS
The authors declare no competing interests.

Lead contact
Further information and requests should be directed to Mohamed A. Almarri (ma17@sanger.ac.uk).

Materials availability
This study did not generate new reagents.
Data and code availability Raw read alignments are available from the European Nucleotide Archive (ENA) under study accession number ENA:ERP110713. Phased VCFs are available on ftp://ngs.sanger.ac.uk/production/appg/.

EXPERIMENTAL MODEL AND SUBJECT DETAILS
This study was approved by Dubai Scientific Research Ethics Committee (DSREC-SR-02/2018_01) and by the Wellcome Sanger Institute Human Materials and Data Management Committee (HMDMC 18/026). All individuals who donated samples for this project were interviewed and provided consent for participation and were recruited in the UAE. We use the term 'Arabian' in this study to refer to samples from the Arabian Peninsula (Emirati, Saudi and Yemen), Levantine for Syrians and Jordanians, and Iraqi-Arabs and Iraqi-Kurds for samples from Iraq. Saliva samples were collected using the Oragene DNA kits (OG-600) and DNA was subsequently extracted using the QIAGEN MagAttract HMW kit (Cat No. 67563). Fragment sizes and quality were determined through a pulsed-field capillary electrophoresis (Femto Pulse system). Libraries were prepared using 10X Genomics Chromium kits and each sample was sequenced in a separate lane on a HiSeq X instrument.

METHOD DETAILS
Samples processing and quality control We ran the Long Ranger pipeline (version 2.2.2, using GATK v3.7) to process raw fastq files into phased BAM files and phased VCF files. The average sequencing depth for all samples was 32x, median 31x, calculated using covstats (https://github.com/brentp/ goleft/) on the phased BAMs. For each VCF we assessed the number of phased variants through summary.csv file output by Long Ranger, we found on average $98% of variants to be physically-phased in each sample. For each VCF we assessed the quality of variant calls output by Long Ranger using the QUALITY filter for each variant. The pipeline uses the haplotype structure informed by the physical phasing to tag variants that are likely to be false positives, as each haplotype can only have one allele. We find that variants that do not have a PASS quality label tend to have low Ts/Tv values, suggesting they contain false positives. We used a stringent filter by setting all non-PASS variants to missing and merged all samples using bcftools v1.9 merge option À0. We removed variants that show excessive heterozygosity as calculated by bcftools ExcHet tag (< 1e-6) and then set any variant with genotype quality (GQ) < 20 and variants located in regions more than twice the average sample depth to missing. The final dataset composed of 23.1 million single nucleotide variants (SNVs). The Ts/Tv after quality control was 1.97, and remained consistent throughout different allele frequency bins suggesting that the variants are of high quality. The TS/TV for all newly identified variants outside the accessibility mask is 1.72, while the Het/Hom for the newly identified variants (> 1% AF) outside the strict mask is 2.08 across all samples. We then examined possible relatedness in our dataset using the genome option in plink-v1.9 (Chang et al., 2015) calculated using a linkage disequilibrium pruned set of 834k biallelic SNVs (minor allele frequency > 5%, missingness < 2%, -indep-pairwise 50 5 0.5). We excluded one sample from a pair showing PI_HAT > 0.15, leaving 136 samples for analysis.
(2020), we also ran IBDMix to identify 'Denisovan' segments in African populations and masked these regions in non-Africans as they are likely to be enriched for incomplete lineage sorting. We filtered the remaining segments using a minimum size threshold of 50kb and LOD score higher than 4.
We also ran Sprime (Browning et al., 2018) on a similar dataset as above but without excluding CpG sites, regions of segmental duplications and the archaic genome accessibility masks ( Figure S6). As Sprime requires non-missing genotypes, we removed variants that were > 5% missing and imputed the remaining missing variants using Eaglev2.4.1 . We set all non-Middle Eastern samples from the HGDP as outgroup (768 samples) and ran Sprime for each Arabian population. We filtered the output using a score threshold of 150,000.
We applied MSMC2 using 4 haplotypes (2 diploid samples) to examine the separation history between our populations and the high coverage Vindija Neanderthal (Prü fer et al., 2014) as we did in our previous study (Bergströ m et al., 2020). Briefly, this analysis exploits the fact that the Vindija Neanderthal shows extremely low heterozygosity, which renders much of the genome homozygous and essentially phased. We used the -skipAmbiguous option to exclude sites with unknown phase and ran MSMC2 using the same parameters previously stated.

Selection
We used the Relate Selection Test in RELATE v1.1  to look for lineages that spread faster than competing lineages. At every site, all variants are required to be phased to perform this test and our relatively stringent quality control may set some variants as missing (for e.g., if a sample had a duplication at a locus, variants within the region will be set as missing because of our depth filter), so we relaxed the depth filter for this test. In addition, as the 10X linked-read technology phases $98% of variants, we used BEAGLEv4.0 (Browning and Browning, 2007) to statistically phase the remaining variants using the gtgl option only for this specific selection test. We set the option usephase = true to take into account the physical-phasing already provided in the VCF. We first ran RELATE v1.1 on 272 haplotypes using the same parameters described in the demographic history section. We extracted the genealogies of the Arabian samples and used the output of the previous step as input to the DetectSelection.sh script accounting for the population history of the populations using the option -m 1.25e-8 -years_per_gen 29. From the resulting .sele file, we extracted p values from the column ''when_mutation_has_freq2'' which tests for evidence of selection over the lifetime of a particular variant. We were conservative and only included variants that show significance at a ''genome-wide threshold'' of p < 5e-8. This test for significance has been shown to be well calibrated , but to even further refine and understand the evolutionary history of the variant we used CLUES (Stern et al., 2019; https://github.com/35ajstern/clues). From the output of Relate above, we ran the Sam-pleBranchLengths.sh script to sample branch lengths from the posterior in order to account for uncertainty. We ran 100 samples (-num_samples 100) using a mutation rate of 1.25e-8 and accounted for the population size history by supplied the .coal files from the previous step. We then ran CLUES (inference.py script) with the option -coal {.coal file} to again account for population size changes. We fine-mapped variants using the likelihood ratio statistic produced by CLUES as suggested by Stern et al. (2019) and focused on variants that show moderate to strong selection (s > 0.005). We used the plot_traj.py script to plot the results.
To test for polygenic selection, we used PALM (Stern et al., 2021; https://github.com/35ajstern/palm). We avoided the use of GWAS summary statistics that were calculated from meta-analysis, due to the potential effect of uncorrected population stratification. We extracted GWAS summary statistics performed on the UK BioBank (UKBB; (Bycroft et al., 2018) downloaded from (https:// alkesgroup.broadinstitute.org/UKBB/UKBB_409K/ - (Gazal et al., 2018); https://alkesgroup.broadinstitute.org/UKBB/LTFH/ sumstats/ - (Hujoel et al., 2020) ; and from the Neale lab Imputed v3 dataset http://www.nealelab.is/uk-biobank/). These statistics were nominally corrected for population structure using either a family history-based approach, fixed PCs, or a linear mixed model. For each trait investigated, we split the genome into 1,700 approximately independent blocks (Berisa and Pickrell, 2016) and selected the variant with the lowest p value within each block for analysis. We chose to be conservative by only including blocks with variants that were genome-wide significant (p < 5e-8), as potentially uncorrected population structure is not expected to produce such highly significant values. Moreover, the method we use, PALM, has been shown to perform well even with some uncorrected GWAS stratification (Stern et al., 2021). Variants were filtered for minor allele frequency > 5%, Rsq > 0.5, INFO score > 0.8, and excluded indels. For each variant passing the previous thresholds, we sampled branch lengths as done for CLUES and estimated selection likelihoods with the lik.py script using the options-coal {.coal file} to account for population size changes and options -K 1 -kappa 3 to specifically test for selection over the past 2000 years, assuming a generation time of 29 years. We then ran palm.py to test for polygenic selection using the option -B 1000 (number of bootstraps). To further explore the choice of significance threshold, and potential effects of uncorrected population structure (variants passing a higher significance threshold are likely to be less biased by uncorrected Figure S1. Population structure and admixture, related to Figure 1 Top: Principal component analysis. Plot similar to Figure 1D but magnifying the modern Middle Eastern cluster and also including other subpopulations (e.g., EmiratiB and QatariB). Bottom: Testing for recent admixture using modern population as sources with GLOBETROTTER. Co-ancestry curves showing relative probability of jointly copying two chunks from donors at varying genetic distances. The curves fit an exponential decay (1-date green line, 2-date red line). The positive slope implies that these donors represent potential proxies to the admixing sources. The estimated admixture date is illustrated on the left of each figure, g for generations. We find that the two putative sources are always a Middle Eastern and an East African population. The dates are in general agreement with MALDER (Table S1). The Iraqi_Kurds are notable for not showing evidence of recent admixture. Figure S2. Y chromosome phylogeny, related to Figure 2 We merged our dataset (samples in Blue) with Haber et al., 2019 (samples in Red) and Hallast et al., 2020 (Samples in Green). We display common haplogroups found in our dataset (A) J1, (B) E1b1 and (C) L-T. Numbers at each node represent coalescence date in thousand years with 95% confidence intervals in brackets. Figure S3. qpGraph alternative models for population formation in the Middle East and automatically fitting admixture graphs, related to  (C) We show a semi-automatically fitted graph. We started with a base-graph of the ancient populations based on previous knowledge Haber et al., 2017); this graph has an outlier Z-score = 2.06. We then used qpBrute (Ní Leathlobhair et al., 2018;Liu et al., 2019) to fit the EmiratiA and we obtained a graph with no outliers showing EmiratiA descended from a mixture of Natufian-related and Sidon_BA-related ancestries. We then used this new graph as a base and added the modern Lebanese. We found that the graph with the lowest Z-score shown here was identical to our  Figure S6. Neanderthal introgressed segments common in Arabia but rare globally identified using Sprime, related to Figures 5A and 5B

Article
Top: 496kb segment on chromosome 13 present at~20% frequency in Saudi populations but rare globally (Global 1000G Project = 0.02%) and overlapping GPC5, a gene expressed in brain tissues. Bottom: 499kb segment on chromosome 4 that reaches~20% frequency in EmiratiA and overlaps CFAP299 expressed in the testes with a role in spermatogenesis, and BMP3, a cytokine which induces cartilage and bone development (Global 1000G Project < 0.05%). We searched for functional variants within these haplotypes but did not find any amino acid changes within canonical transcripts, with most substitutions limited to introns. Variants showing extreme branch statistics highlighted. Red line illustrates the top 99.999% quantile. Note the different y axis scales. rs2814778 is the variant discussed in the main text found at high frequencies in Yemenis that results in the Duffy null genotype. rs35040 shows strong differentiation in Emiratis and is an eQTL for DDX11 in multiple tissues. For both Emiratis and Saudis, we find a strong signal of differentiation at a 97kb haplotype on chromosome 7. Variants on this haplotype (rs1734235) almost reach fixation (97% and 85%, in Emiratis and Saudis respectively) and are associated with increased expression of the lincRNA AC003088.1 in cultured fibroblasts (GTEx Analysis Release V8; The GTEx Consortium, 2020).