Related Experiment Video
Updated: Aug 9, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
On the complexity of fundamental computational problems in pedigree analysis
Antonio Piccolboni1, Dan Gusfield
1Computer Science Department, University of California, Davis 95616, USA. antonio-piccolboni@affymetrix.com
Summary
Pedigree analysis for gene discovery involves complex computational problems. Researchers found these problems remain NP-hard, even without inbreeding loops, impacting genetic trait and disease research.
Area of Science:
- Genetics and Bioinformatics
- Computational Biology
- Disease Gene Discovery
Background:
- Pedigree analysis is crucial for identifying genes linked to diseases and traits.
- Current methods often rely on solving computationally intensive problems.
- Understanding the complexity of these problems is vital for efficient genetic research.
Purpose of the Study:
- To analyze the computational complexity of two core problems in pedigree analysis.
- To determine if simplifying assumptions in pedigree structures affect problem difficulty.
- To provide insights into the inherent computational challenges of gene localization.
Main Methods:
- Complexity analysis of algorithms used in pedigree analysis.
- Theoretical examination of computational problem-solving within genetic contexts.
- Evaluation of problem hardness under specific pedigree constraints (absence of inbreeding loops).
Main Results:
- Both analyzed pedigree analysis problems were proven to be NP-hard.
- This NP-hard complexity persists even in pedigrees lacking inbreeding loops.
- The findings highlight significant computational hurdles in gene mapping.
Conclusions:
- The computational intensity of pedigree analysis is a fundamental challenge.
- Gene localization efforts using these methods face inherent complexity.
- Further research may be needed to develop more tractable approaches for complex genetic trait analysis.
More Related Videos
Related Concept Videos
01:35Pedigree Analysis
Overview
01:49Probability Laws
Overview
01:49Hardy-Weinberg Principle
Diploid organisms have two alleles of each gene, one from each parent, in their somatic cells. Therefore, each individual contributes two alleles to the gene pool of the population. The gene pool of a population is the sum of every allele of all genes within that population and has some degree of variation. Genetic variation is typically expressed as a relative frequency, which is the percentage of the total population that has a given allele, genotype or phenotype.In the early 20th century,...
01:35Pedigree Analysis
Overview
01:43Incomplete Dominance
Gregor Mendel's work (1822 - 1884) was primarily focused on pea plants. Through his initial experiments, he determined that every gene in a diploid cell has two variants called alleles inherited from each parent. He suggested that amongst these two alleles, one allele is dominant in character and the other recessive. The combination of alleles determines the phenotype of a gene in an organism.
02:54Evolutionary Relationships through Genome Comparisons
Genome comparison is one of the excellent ways to interpret the evolutionary relationships between organisms. The basic principle of genome comparison is that if two species share a common feature, it is likely encoded by the DNA sequence conserved between both species. The advent of genome sequencing technologies in the late 20th century enabled scientists to understand the concept of conservation of domains between species and helped them to deduce evolutionary relationships across diverse...