Optimizing Sequencing Resources in Genotyped Livestock Populations Using Linear Programming.

Area of Science:

• Genomics
• Animal Breeding
• Bioinformatics

Background:

• Genome-wide single-nucleotide polymorphisms (SNPs) are crucial for livestock breeding programs.
• Whole-genome sequence data from next-generation sequencing (NGS) offers greater potential than SNP arrays but is costly to obtain for large populations.
• Efficient strategies are needed to allocate sequencing resources for accurate imputation in livestock.

Purpose of the Study:

• To develop and present linear programming applications for optimizing sequencing resource allocation in livestock populations.
• To identify methods for selecting animals to maximize haplotype coverage and common haplotype representation within budget constraints.
• To introduce LPChoose, an open-source program implementing these linear programming strategies.

Main Methods:

• Two linear programming applications were developed for sequencing resource allocation.
• Application 1: Minimizing the number of animals to ensure all population haplotypes are represented.
• Application 2: Selecting animals that maximize the proportion of common population haplotypes under a budget.
• Implementation in the open-source program LPChoose.

Main Results:

• LPChoose demonstrated comparable or superior performance to existing methods in both applications.
• The linear programming approach effectively addresses the challenge of cost-effective whole-genome sequencing for imputation.
• The developed methods provide a framework for efficient sequencing resource allocation.

Conclusions:

• Linear programming offers a powerful and efficient strategy for allocating whole-genome sequencing resources in livestock.
• The LPChoose program provides a practical tool for implementing these optimization methods.
• Further improvements can be achieved through the development of enhanced heuristics for greater utility.