Related Experiment Video
Updated: Jul 7, 2026
08:57
Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
Computational problems in perfect phylogeny haplotyping: typing without calling the allele.
Tamar Barzuza1, Jacques S Beckmann, Ron Shamir
1Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. tamarbarzuza@gmail.com
IEEE/ACM Transactions on Computational Biology and Bioinformatics
|February 5, 2008
Summary
This study reconstructs human genetic haplotypes from less informative XOR-genotypes using a polynomial-time algorithm. It establishes conditions for unique haplotype reconstruction and identifies minimal data needed for accurate determination.
Area of Science:
- Bioinformatics
- Computational Biology
- Population Genetics
Background:
- Haplotypes, represented as binary vectors, are fundamental to understanding genetic variation.
- The perfect phylogeny (PP) haplotyping problem is crucial for studying population evolution.
- Existing methods often require 'full' genotypes, which can be experimentally costly.
Purpose of the Study:
- To develop a method for reconstructing haplotypes from less informative XOR-genotypes.
- To determine if these reconstructed haplotypes can map onto a perfect phylogeny (PP) tree.
- To investigate conditions for unique haplotype and tree reconstruction.
Main Methods:
- Utilized XOR-genotypes as input, a less informative data type than full genotypes.
- Employed Gusfield's ideas and reduced the problem to the graph realization problem.
- Analyzed conditions for the uniqueness of the resulting perfect phylogeny tree and haplotypes.
Main Results:
- Developed a polynomial-time algorithm to solve the XOR-genotype haplotyping problem.
- Demonstrated that tree uniqueness implies uniquely determined haplotypes, with conditions for uniqueness provided.
- Showed that two or three full genotypes are sufficient for complete haplotype reconstruction.
Conclusions:
- The study presents an efficient method for haplotype reconstruction from limited data.
- It offers insights into the relationship between perfect phylogeny tree structure and haplotype uniqueness.
- A linear algorithm is provided for identifying genotypes necessary for full haplotype determination.
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:28Microbial Phylogeny
Understanding the evolutionary relationships among microorganisms is fundamental to microbial ecology and taxonomy. Phylogenetic trees are essential tools for inferring these relationships, relying primarily on comparative analyses of molecular sequences such as DNA, RNA, or proteins. In microbial studies, these trees typically depict the evolutionary paths of diverse bacterial and archaeal species by mapping genetic differences accumulated over time.Phylogenetic trees are composed of tips,...
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...
01:29Modern Molecular Taxonomy
Advancements in molecular biology have revolutionized the identification and characterization of bacteria, with multiple methods leveraging DNA sequencing for enhanced precision. As sequencing technologies improve and costs decline, these approaches are increasingly used in clinical, environmental, and evolutionary studies.Multilocus Sequence Typing (MLST) examines several housekeeping genes, essential chromosomal genes encoding cellular functions, to distinguish strains. Approximately...
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...
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,...