Linear Time Algorithms to Construct Populations Fitting Multiple Constraint Distributions at Genomic Scales.

Abstract

Computer simulations can be used to study population genetic methods, models, and parameters, as well as to predict potential outcomes. For example, in plant populations, predicting the outcome of breeding operations can be studied using simulations. In-silico construction of populations with pre-specified characteristics is an important task in breeding optimization and other population genetic studies. We present two linear time Simulation using Best-fit Algorithms (SimBA) for two classes of problems where each co-fits two distributions: SimBA-LD fits linkage disequilibrium and minimum allele frequency distributions, while SimBA-hap fits founder-haplotype and polyploid allele dosage distributions. An incremental gap-filling version of previously introduced SimBA-LD is here demonstrated to accurately fit the target distributions, allowing efficient large scale simulations. SimBA-hap accuracy and efficiency is demonstrated by simulating tetraploid populations with varying numbers of founder haplotypes, we evaluate both a linear time greedy algoritm and an optimal solution based on mixed-integer programming. SimBA is available on http://researcher.watson.ibm.com/project/5669.

• Authors: Enrico Siragusa, Niina Haiminen, Filippo Utro, Laxmi Parida
• Journal: IEEE/ACM transactions on computational biology and bioinformatics (IEEE/ACM Trans Comput Biol Bioinform) 2019 Jul-Aug Vol. 16 Issue 4 Pg. 1132-1142 ISSN: 1557-9964 [Electronic] United States
• PMID: 28991752 (Publication Type: Journal Article)

Chemical References

• DNA, Plant

Topics

• Algorithms
• Alleles
• Computational Biology (methods)
• Computer Simulation
• DNA, Plant (genetics)
• Gene Dosage
• Gene Frequency
• Genes, Plant
• Genomics
• Haplotypes
• Humans
• Linear Models
• Linkage Disequilibrium
• Models, Genetic
• Polymorphism, Single Nucleotide