Disk-covering method

A disk-covering method is a divide-and-conquer meta-technique for large-scale phylogenetic analysis which has been shown to improve the performance of both heuristics for NP-hard optimization problems and polynomial-time distance-based methods. Disk-covering methods are a meta-technique in that they have flexibility in several areas, depending on the performance metrics that are being optimized for the base method. Such metrics can be efficiency, accuracy, or sequence length requirements for statistical performance. There have been several disk-covering methods developed, which have been applied to different "base methods". Disk-covering methods have been used with distance-based methods (like neighbor joining) to produce "fast-converging methods"^{[1] [2][3]}, which are methods that will reconstruct the true tree from sequences that have at most a polynomial number of sites.

A disk-covering method has four steps:

1. Decomposition: Compute a decomposition of the dataset into overlapping subsets.
2. Solution: Construct trees on the subsets using a base method.
3. Merge: Use a supertree method to merge the trees on the subsets into a tree on the full dataset.
4. Refinement: If the tree obtained in the merge is not fully resolved, then resolve it further into a binary tree so that it optimizes some desired objective criterion.

The major use of any disk-covering method is that of the "Rec-I-DCM3" disk-covering method ^[4], which has been used to speed-up maximum likelihood and maximum parsimony analyses, and are available through the NSF-funded CIPRES project (www.phylo.org). However, disk-covering methods have also been used for estimating evolutionary trees from gene order data ^[5]

References

1. ^ D. Huson, S. Nettles and T. Warnow. (1999). Disk-covering, a fast-converging method for phylogenetic tree reconstruction. Journal of Computational Biology, 6:369-386.
2. ^ L. Nakhleh, U. Roshan, K. St. John, J. Sun and T. Warnow. (2001). Designing fast converging phylogenetic methods. In Proc. 9th Int'l Conf. on Intelligent Systems for Molecular Bioology (ISMB '01), volume 17 of Bioinformatics, pp S190-S198. Oxford U. Press.
3. ^ T. Warnow, B. Moret and K. St. John. (2001). Absolute convergence: True trees from short sequences. In Proc. 12th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA '01), pp. 186-195. SIAM Press, 2001.
4. ^ U. Roshan, B.M.E. Moret, T. Warnow and T.L. Williams. (2004). Rec-I-DCM3: a fast algorithmic technique for reconstructing large phylogenetic trees. In Proceedings of the IEEE Computational Systems Bioinformatics conference (CSB), Stanford, California, USA.
5. ^ * J. Tang and B. Moret. (2003). Scaling up accurate phylogenetic reconstruction from gene-order data. In Proc. 11th Int'l Conf. on Intelligent Systems for Molecular Biology ISMB '03, volume 19 (Suppl. 1) of Bioinformatics, pp i305 - i312.

• T. Warnow. 2005. Large-scale phylogenetic reconstruction. Book chapter, in S. Aluru (editor), Handbook of Computational Biology, Chapman & Hall, CRC Computer and Information Science Series, December 2005.

_

This bioinformatics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Bioinformatics stubs Computational phylogenetics Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Kenneth Kannappan Indira Jaising Look at other dictionaries: Disk covering problem — The disk covering problem was proposed by C. T. Zahn in 1962. Given an integer n, the problem asks for the smallest real number r(n) such that n disks of radius r(n) can be arranged in such a way as to cover the unit disk. The best solutions to… …   Wikipedia Disk encryption — uses disk encryption software or hardware to encrypt every bit of data that goes on a disk or disk volume. Disk encryption prevents unauthorized access to data storage. The term full disk encryption (or whole disk encryption) is often used to… …   Wikipedia Nebra sky disk — The Nebra Sky Disk. The Nebra Sky Disk is a bronze disk of around 30 cm diameter, with a blue green patina and inlaid with gold symbols. These are interpreted generally as a sun or full moon, a lunar crescent, and stars (including a cluster… …   Wikipedia Quantitative comparative linguistics — is a branch of comparative linguistics that applies mathematical models to the problem of classifying language relatedness. This includes the use of computational phylogenetics and cladistics to define an optimal tree (or network) to represent a… …   Wikipedia List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia Color television — Title card for NBC, promoting their broadcast in RCA color . Color television is part of the history of television, the technology of television and practices associated with television s transmission of moving images in color video. In its most… …   Wikipedia animal development — Introduction  the processes that lead eventually to the formation of a new animal starting from cells derived from one or more parent individuals. Development thus occurs following the process by which a new generation of organisms is produced by …   Universalium arts, East Asian — Introduction       music and visual and performing arts of China, Korea, and Japan. The literatures of these countries are covered in the articles Chinese literature, Korean literature, and Japanese literature.       Some studies of East Asia… …   Universalium metalwork — metalworker, n. /met l werrk /, n. objects made of metal. [1840 50; METAL + WORK] * * * Useful and decorative objects fashioned of various metals. The oldest technique is hammering. After с 2500 BC, casting was also used, molten metal being… …   Universalium optics — /op tiks/, n. (used with a sing. v.) the branch of physical science that deals with the properties and phenomena of both visible and invisible light and with vision. [1605 15; < ML optica < Gk optiká, n. use of neut. pl. of OPTIKÓS; see OPTIC,… …   Universalium 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”