Related Experiment Video
Updated: Jun 3, 2026
11:41
Mapping Mammalian 3D Genome Interactions with Micro-C-XL
Published on: November 3, 2023
Faster exact maximum parsimony search with XMP
W Timothy J White1, Barbara R Holland
1Institute of Fundamental Sciences, Massey University, Palmerston North, New Zealand. w.t.white@massey.ac.nz
Bioinformatics (Oxford, England)
|March 30, 2011
Summary
Maximum parsimony (MP) tree searches are computationally intensive. XMP is a new program offering faster serial and scalable parallel versions for exact MP phylogenetic tree analysis.
Area of Science:
- Computational Biology
- Phylogenetics
- Bioinformatics
Background:
- Maximum parsimony (MP) is a key method for phylogenetic tree evaluation.
- Exact MP searches are NP-complete, limiting analysis to ~30 taxa due to computational demands.
- Existing software does not effectively utilize parallel processing.
Purpose of the Study:
- Introduce XMP, a novel program for exact maximum parsimony tree searches.
- Improve the efficiency and scalability of phylogenetic analysis using MP.
Main Methods:
- Developed serial and parallel versions of the XMP program.
- Implemented a work-stealing algorithm for efficient parallelization on distributed-memory systems.
- Optimized the inner loop with SSE2 for enhanced CPU performance.
Main Results:
- XMP's serial version outperforms existing software in most tests.
- The parallel version demonstrates high efficiency scaling to hundreds of CPUs.
- Optimized inner loop provides significant speedup on compatible processors.
Conclusions:
- XMP offers a significant advancement in computational efficiency for exact MP phylogenetic tree searches.
- The parallel version enables analysis of larger datasets than previously feasible.
- XMP is freely available, promoting wider use in phylogenetic research.
Related Concept Videos
02:51Multi-species Conserved Sequences
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
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:05Maxam-Gilbert Sequencing
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...