PMSeeker: A Scheme Based on the Greedy Algorithm and the Exhaustive Algorithm to Screen Low-Redundancy Marker Sets...

Parentage assignment is a genetic test that utilizes genetic characteristics, such as molecular markers, to identify the parental relationships within populations, which, in commercial fish farming, are almost always large and where full information on potential parents is known. To accurately find the true parents, the genotypes of all loci in the parentage marker set (PMS) are required for each individual being tested. With the same accuracy, a PMS containing a smaller number of markers will undoubtedly save experimental costs. Thus, this study established a scheme to screen low-redundancy PMSs using the exhaustive algorithm and greedy algorithm. When screening PMSs, the greedy algorithm selects markers based on the parental dispersity index (PDI), a uniquely defined metric that outperforms the probability of exclusion (PE). With the conjunctive use of the two algorithms, non-redundant PMSs were found for more than 99.7% of solvable cases in three groups of random sample experiments in this study. Then, a low-redundancy PMS can be composed using two or more of these non-redundant PMSs. This scheme effectively reduces the number of markers in PMSs, thus conserving human and experimental resources and laying the groundwork for the widespread implementation of parentage assignment technology in economic species breeding.