Related Experiment Video
Updated: Jun 22, 2026
12:00
A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
An almost linear time algorithm for a general haplotype solution on tree pedigrees with no recombination and its
1Department of Electrical Engineering and Computer Science, Case Western Reserve University, 10900 Euclid Ave, Cleveland, Ohio 44106, USA. xin.li2@case.edu
Journal of Bioinformatics and Computational Biology
|June 10, 2009
Summary
This study presents a fast and efficient algorithm for haplotype inference using pedigree data and the zero recombination assumption. The method significantly improves upon existing algorithms for genetic analysis.
Area of Science:
- Computational Biology
- Genetics
- Bioinformatics
Background:
- Haplotype inference from pedigree data is crucial for genetic studies.
- The zero recombination assumption is valid for tightly linked markers like single nucleotide polymorphisms (SNPs) over large chromosome segments.
Purpose of the Study:
- To develop a mathematically rigorous and efficient algorithm for haplotype inference under the zero recombination assumption.
- To improve upon existing methods in terms of speed and accuracy for genetic data analysis.
Main Methods:
- Formulating genotype constraints as a linear system of inheritance variables.
- Utilizing disjoint-set data structures to encode connectivity, detect constraints, and check consistency.
- Extending the algorithm to handle looped pedigrees and missing data.
Main Results:
- Achieved nearly linear time complexity (O(mn . alpha(n))) for tree pedigrees without missing data.
- Demonstrated correct identification of all 0-recombinant solutions with high efficiency.
- Showcased 10 to 10(5)-fold improvements compared to two popular existing algorithms.
Conclusions:
- The developed algorithm provides a significant advancement in haplotype inference efficiency and accuracy.
- The method is robust and performs well on various pedigree structures and data completeness.
- Implementation in C++ and inclusion in the PedPhase package facilitates practical application.
Related Concept Videos
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...
01:35Pedigree Analysis
Overview
01:35Pedigree Analysis
Overview
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
03:21Phylogenetic Trees
Phylogenetic trees come in many forms. It matters in which sequence the organisms are arranged from the bottom to the top of the tree, but the branches can rotate at their nodes without altering the information. The lines connecting individual nodes can be straight, angled, or even curved.The length of the branches can depict time or the relative amount of change among organisms. For instance, the branch length might indicate the number of amino acid changes in the sequence that underlies the...