Genetic diversity and haplotype structure of 21 Y‐STRs,including nine noncore loci,in South Tunisian Population: Forensic relevance

Y chromosome STRs (Y‐STRs) are being used frequently in forensic laboratories. Previous studies of Y‐STR polymorphisms in different groups of the Tunisian population identified low levels of diversity and discrimination capacity (DC) using various commercial marker sets. This definitely limits the use of such systems for Y‐STRs genotyping in Tunisia. In our investigation on South Tunisia, 200 unrelated males were typed for the 12 conventional Y‐STRs included in the PowerPlex® Y System. Additional set of nine noncore Y‐STRs including DYS446, DYS456, DYS458, DYS388, DYS444, DYS445, DYS449, DYS710, and DYS464 markers were genotyped and evaluated for their potential in improving DC. Allele frequency, gene diversity, haplotype diversity (HD), and DC calculation revealed that DYS464 was the most diverse marker followed by DYS710 and DYS449 markers. The standard panel of 12 Y‐STRs (DC = 80.5%) and the nine markers were combined to obtain DC of 99%. Among the 198 different haplotypes observed, 196 haplotypes were unique (HD = 99.999). Out of the nine noncore set, six Y‐STRs (DYS458, DYS456, DYS449, DYS710, DYS444, and DYS464) had the greatest impact on enhancing DC. Our data provided putative Y‐STRs combination to be used for genetic and forensic applications.     

Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.     

The haplotype assembly model with genotype information and iterative local-exhaustive search algorithm

The minimum error correction (MEC) model for haplotype reconstruction is efficient only when the error rate in SNP fragments is low. In order to improve reconstruction rate, additional genotype information is added into MEC model as an extension to MEC model. In this paper, we first establish a new mathematical model for haplotype assembly problem with genotype information. Several properties of the mathematical model are proved. Then an iterative local-exhaustive search algorithm is proposed based on the model and its properties. The main idea is to find the optimal pair among 2(l-1) (l denotes the number of heterozygous sites of a genotype) haplotype pairs by performing local exhaustive search for the promising haplotype pair step by step. By experiments and comparison, extensive numerical results on real data and simulated data indicate that our algorithm outperforms the other algorithms in terms of efficiency and robustness.     

AROHap: An effective algorithm for single individual haplotype reconstruction based on asexual reproduction optimization

In this paper, a method for single individual haplotype (SIH) reconstruction using Asexual reproduction optimization (ARO) is proposed. Haplotypes, as a set of genetic variations in each chromosome, contain vital information such as the relationship between human genome and diseases. Finding haplotypes in diploid organisms is a challenging task. Experimental methods are expensive and require special equipment. In SIH problem, we encounter with several fragments and each fragment covers some parts of desired haplotype. The main goal is bi-partitioning of the fragments with minimum error correction (MEC). This problem is addressed as NP-hard and several attempts have been made in order to solve it using heuristic methods. The current method, AROHap, has two main phases. In the first phase, most of the fragments are clustered based on a practical metric distance. In the second phase, ARO algorithm as a fast convergence bio-inspired method is used to improve the initial bi-partitioning of the fragments in the previous step. AROHap is implemented with several benchmark datasets. The experimental results demonstrate that satisfactory results were obtained, proving that AROHap can be used for SIH reconstruction problem.     

Allele and haplotype diversity of new multiplex of 19 ChrX‐STR loci in Han population from Guanzhong region (China)

X‐chromosomal short tandem repeats (X‐STRs) have been proved to be useful for some deficiency paternity cases in recent years. Here, we studied the genetic polymorphisms of 19 X‐STR loci (DXS10148‐DXS10135‐DXS8378, DXS10159‐DXS10162‐DXS10164, DXS7132‐DXS10079‐DXS10074‐DXS10075, DXS6809‐DXS6789, DXS7424‐DXS101, DXS10103‐HPRTB‐DXS10101 and DXS7423‐DXS10134) in 252 male and 222 female individuals from Guanzhong Han population, China. No deviation for all 19 loci was observed from the Hardy–Weinberg equilibrium. The polymorphism information content values of the panel of 19 loci were more than 0.5 with the exception of the locus DXS7423. The combined power of discrimination were 0.9999999999999999999994340 in females and 0.9999999999997662 in males, respectively; and the combined mean exclusion chances were 0.999999993764 in duos and 0.999999999997444 in trios, respectively. The haplotype diversities for all the seven clusters of linked loci were more than 0.9. The results showed that the panel of 19 X‐STR loci were powerful for forensic applications in Guanzhong Han population. Locus by locus population comparisons showed significant differences at more than seven loci between Guanzhong Han population and the groups from North America, Europe and Africa.     

A clustering algorithm based on two distance functions for MEC model

Haplotype reconstruction, based on aligned single nucleotide polymorphism (SNP) fragments, is to infer a pair of haplotypes from localized polymorphism data gathered through short genome fragment assembly. This paper first presents two distance functions, which are used to measure the difference degree and similarity degree between SNP fragments. Based on the two distance functions, a clustering algorithm is proposed in order to solve MEC model. The algorithm involves two sections. One is to determine the initial haplotype pair, the other concerns with inferring true haplotype pair by re-clustering. The comparison results prove that our algorithm utilizing two distance functions is effective and feasible.     

Haplotype assembly from aligned weighted SNP fragments

Given an assembled genome of a diploid organism the haplotype assembly problem can be formulated as retrieval of a pair of haplotypes from a set of aligned weighted SNP fragments. Known computational formulations (models) of this problem are minimum letter flips (MLF) and the weighted minimum letter flips (WMLF; Greenberg et al. (INFORMS J. Comput. 2004, 14, 211-213)). In this paper we show that the general WMLF model is NP-hard even for the gapless case. However the algorithmic solutions for selected variants of WMFL can exist and we propose a heuristic algorithm based on a dynamic clustering technique. We also introduce a new formulation of the haplotype assembly problem that we call COMPLETE WMLF (CWMLF). This model and algorithms for its implementation take into account a simultaneous presence of multiple kinds of data errors. Extensive computational experiments indicate that the algorithmic implementations of the CWMLF model achieve higher accuracy of haplotype reconstruction than the WMLF-based algorithms, which in turn appear to be more accurate than those based on MLF.     

Genetic polymorphism of 13 non‐CODIS STR loci in three national populations from China

The aim of this study was to investigate a 13 non‐CODIS STR loci database using three national populations from China. A new multiplex PCR system that simultaneously amplified 13 loci in the same PCR reaction was developed. This multiplex system included the 13 STR markers (D3S2402, D3S2452, D3S1766, D3S4554, D3S2388, D3S3051, D3S3053, D4S2364, D4S2404, AC001348A, AC001348B, D17S975, and D17S1294), which were successfully analyzed by using 441 DNA samples from three national populations in China (154 Mongol, 177 Kazakh, and 110 Uigur). Allele frequencies and mutation rates of the 13 non‐CODIS STR loci were investigated. A total of 4–10 alleles at each locus were observed and altogether 84, 88, and 87 alleles for the all selected loci were found in the Mongol, Kazakh, and Uigur, respectively. Eight mutations were detected from the 13 selected loci in 9880 meioses in kinship cases. These results indicate that this multiplex system may provide significant polymorphic information for kinship testing and relationship investigations.     

Genetic diversity and haplotype structure of 24 Y‐chromosomal STR in Chinese Hui ethnic group and its genetic relationships with other populations

In the present study, 24 Y‐chromosomal short tandem repeat (Y‐STR) loci were analyzed in 115 unrelated Hui male individuals from Haiyuan county or Tongxin county, Ningxia Hui Autonomous Region, China, to evaluate the forensic application of the 24 STR loci and to analyze interpopulation differentiations by making comparisons between the Hui group data and previously published data of other 13 populations. A total of 115 different haplotypes were observed on these 24 Y‐STR loci. The gene diversities ranged from 0.4049 (DYS437) to 0.9729 (DYS385a, b). The overall haplotype diversity was 1 at AGCU 24 Y‐STR loci level, while the values were reduced to 0.999237, 0.996949, and 0.996644 at the Y‐filer 17 loci, 11 Y‐STR loci of extended haplotype and 9 Y‐STR loci of minimal haplotype levels, respectively; whereas, haplotype diversity for additional 7 loci (not included in Y‐filer 17 loci) was 0.995271. The pairwise F_ST, multidimensional scaling plot and neighbor‐joining tree indicated the Hui group had the closest genetic relationship with Sala in the paternal lineage in the present study. In summary, the results in our study indicated the 24 Y‐STRs had a high level of polymorphism in Hui group and hence could be a powerful tool for forensic application and population genetic study.     

Efficient haplotype inference algorithms in one whole genome scan for pedigree data with non-genotyped founders

An efficient rule-based algorithm is presented for haplotype inference from general pedigree genotype data, with the assumption of no recombination. This algorithm generalizes previous algorithms to handle the cases where some pedigree founders are not genotyped, provided that for each nuclear family at least one parent is genotyped and each non-genotyped founder appears in exactly one nuclear family. The importance of this generalization lies in that such cases frequently happen in real data, because some founders may have passed away and their genotype data can no longer be collected. The algorithm runs in O（m^3n^3） time, where m is the number of single nucleotide polymorphism （SNP） loci under consideration and n is the number of genotyped members in the pedigree. This zero-recombination haplotyping algorithm is extended to a maximum parsimoniously haplotyping algorithm in one whole genome scan to minimize the total number of breakpoint sites, or equivalently, the number of maximal zero-recombination chromosomal regions. We show that such a whole genome scan haplotyping algorithm can be implemented in O（m^3n^3） time in a novel incremental fashion, here m denotes the total number of SNP loci along the chromosome.