TAILIEUCHUNG - Báo cáo sinh học: "distance between two general trees"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: distance between two general trees. | Nielsen et al. Algorithms for Molecular Biology 2011 6 15 http content 6 1 15 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access A sub-cubic time algorithm for computing the quartet distance between two general trees Jesper Nielsen1 2 Anders K Kristensen2 Thomas Mailund1 and Christian NS Pedersen1 2 Abstract Background When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure and is the number of quartet topologies that differ between two trees. Results We have derived a new algorithm for computing the quartet distance between a pair of general trees . trees where inner nodes can have any degree 3. The time and space complexity of our algorithm is sub-cubic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm so far for computing the quartet distance between general trees independent of the degree of the inner nodes. Conclusions We have implemented our algorithm and two of the best competitors. Our new algorithm is significantly faster than the competition and seems to run in close to quadratic time in practice. Background The evolutionary relationship between a set of species is conveniently described as a tree where the leaves represent the species and the inner nodes speciation events. Using different inference methods to infer such trees from biological data or using different biological data from the same set of species often yield slightly different trees. To study such differences in a systematic manner one must be able to quantify differences between evolutionary trees using well-defined and efficient methods. One approach for this is to define a distance measure between trees and compare two trees by computing this distance. Several distance measures have been proposed . the symmetric difference 1 the nearest-neighbour interchange 2 .

• Báo cáo khoa học
• Báo cáo sinh học hay
• cách trình bày báo cáo
• báo cáo sinh học
• công trình nghiên cứu sinh học
• tài liệu về sinh học