2016/02/13 by Bonnie Kirkpatrick, Kirkpatrick, Bonnie
Biochemistry, Genetics and Molecular Biology · Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genetic Associations and Epidemiology #Genetic Mapping and Diversity in Plants and Animals #Genomic variations and chromosomal abnormalities #cs.DS
paper · pdf · doi:10.48550/arxiv.1602.04270
arxiv created 2016/02/13 · openalex publication_date 2016/02/13 · arxiv updated 2016/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Pedigrees, or family trees, are graphs of family relationships that are used to study inheritance. A fundamental problem in computational biology is to find, for a pedigree with n individuals genotyped at every site, a set of Mendelian-consistent haplotypes that have the minimum number of recombinations. This is an NP-hard problem and some pedigrees can have thousands of individuals and hundreds of thousands of sites. This paper formulates this problem as a optimization on a graph and introduces a tailored algorithm with a running time of O(n(k+2)m6k) for n individuals, m sites, and k recombinations. Since there are generally only 1-2 recombinations per chromosome in each meiosis, k is small enough to make this algorithm practically relevant.