Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: Constructing majority-rule supertrees. | Dong et al. Algorithms for Molecular Biology 2010 5 2 http www.almob.Org content 5 1 2 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access Constructing majority-rule supertrees Jianrong Dong1 David Fernandez-Baca1 FR McMorris2 Abstract Background Supertree methods combine the phylogenetic information from multiple partially-overlapping trees into a larger phylogenetic tree called a supertree. Several supertree construction methods have been proposed to date but most of these are not designed with any specific properties in mind. Recently Cotton and Wilkinson proposed extensions of the majority-rule consensus tree method to the supertree setting that inherit many of the appealing properties of the former. Results We study a variant of one of Cotton and Wilkinson s methods called majority-rule supertrees. After proving that a key underlying problem for constructing majority-rule supertrees is NP-hard we develop a polynomial-size exact integer linear programming formulation of the problem. We then present a data reduction heuristic that identifies smaller subproblems that can be solved independently. While this technique is not guaranteed to produce optimal solutions it can achieve substantial problem-size reduction. Finally we report on a computational study of our approach on various real data sets including the 121-taxon 7-tree Seabirds data set of Kennedy and Page. Conclusions The results indicate that our exact method is computationally feasible for moderately large inputs. For larger inputs our data reduction heuristic makes it feasible to tackle problems that are well beyond the range of the basic integer programming approach. Comparisons between the results obtained by our heuristic and exact solutions indicate that the heuristic produces good answers. Our results also suggest that the majority-rule approach in both its basic form and with data reduction yields biologically meaningful phylogenies. Background Introduction A supertree method begins with a
