Table_3_Distinguishing HapMap Accessions Through Recursive Set Partitioning in Hierarchical Decision Trees.pdf

The HapMap (haplotype map) projects have produced valuable genetic resources in life science research communities, allowing researchers to investigate sequence variations and conduct genome-wide association study (GWAS) analyses. A typical HapMap project may require sequencing hundreds, even thousands, of individual lines or accessions within a species. Due to limitations in current sequencing technology, the genotype values for some accessions cannot be clearly called. Additionally, allelic heterozygosity can be very high in some lines, causing genetic and sometimes phenotypic segregation in their descendants. Genetic and phenotypic segregation degrades the original accession’s specificity and makes it difficult to distinguish one accession from another. Therefore, it is vitally important to determine and validate HapMap accessions before one conducts a GWAS analysis. However, to the best of our knowledge, there are no prior methodologies or tools that can readily distinguish or validate multiple accessions in a HapMap population. We devised a bioinformatics approach to distinguish multiple HapMap accessions using only a minimum number of genetic markers. First, we assign each candidate marker with a distinguishing score (DS), which measures its capability in distinguishing accessions. The DS score prioritizes those markers with higher percentages of homozygous genotypes (allele combinations), as they can be stably passed on to offspring. Next, we apply the “set-partitioning” concept to select optimal markers by recursively partitioning accession sets. Subsequently, we build a hierarchical decision tree in which a specific path represents the selected markers and the homogenous genotypes that can be used to distinguish one accession from others in the HapMap population. Based on these algorithms, we developed a web tool named MAD-HiDTree (Multiple Accession Distinguishment-Hierarchical Decision Tree), designed to analyze a user-input genotype matrix and construct a hierarchical decision tree. Using genetic marker data extracted from the Medicago truncatula HapMap population, we successfully constructed hierarchical decision trees by which the original 262 M. truncatula accessions could be efficiently distinguished. PCR experiments verified our proposed method, confirming that MAD-HiDTree can be used for the identification of a specific accession. MAD-HiDTree was developed in C/C++ in Linux. Both the source code and test data are publicly available at https://bioinfo.noble.org/MAD-HiDTree/.

单倍型图谱（HapMap，haplotype map）项目已为生命科学研究领域提供了宝贵的遗传资源，助力研究者开展序列变异研究与全基因组关联分析（genome-wide association study，GWAS）。典型的HapMap项目需对某一物种内的数百乃至数千个品系或种质进行测序。受当前测序技术的限制，部分种质的基因型值无法明确完成基因分型。此外，部分品系的等位基因杂合性极高，会导致其后代出现遗传分离，有时还会伴随表型分离。遗传与表型分离会削弱原种质的特异性，导致不同种质间难以区分。因此，在开展全基因组关联分析前，对HapMap种质进行鉴定与验证至关重要。然而，据我们所知，目前尚无能够便捷区分或验证HapMap群体中多种种质的方法或工具。我们提出了一种生物信息学方法，仅需使用最少数量的遗传标记即可区分多种HapMap种质。首先，我们为每个候选标记分配区分得分（distinguishing score，DS），用于衡量其区分种质的能力。该区分得分优先选择纯合基因型（等位基因组合）占比更高的标记，因为这类标记可稳定传递给后代。随后，我们应用“集合划分”理念，通过递归划分种质集合来筛选最优标记。接着，我们构建了层级决策树，其中每条特定路径代表用于区分HapMap群体中不同种质的选定标记与纯合基因型。基于上述算法，我们开发了一款名为MAD-HiDTree（Multiple Accession Distinguishment-Hierarchical Decision Tree）的网络工具，用于分析用户输入的基因型矩阵并构建层级决策树。利用从蒺藜苜蓿HapMap群体中提取的遗传标记数据，我们成功构建了层级决策树，可高效区分初始的262份蒺藜苜蓿种质。聚合酶链式反应（PCR）实验验证了我们提出的方法，证实MAD-HiDTree可用于特定种质的鉴定。MAD-HiDTree基于Linux系统下的C/C++语言开发，其源代码与测试数据均可在https://bioinfo.noble.org/MAD-HiDTree/公开获取。