NDLI: Using Max Cut to Enhance Rooted Trees Consistency

Please wait, while we are loading the content...

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 13

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 12

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 11

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 10

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 9

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 8

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 7

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 6

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 5

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 4

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 3

Issue 4, October 2006

Guest Editor's Introduction to the Special Issue on Computational Biology and Bioinformatics -- Part 1

Using Max Cut to Enhance Rooted Trees Consistency

Pattern Identification in Biogeography

Efficient Detection of Network Motifs

Motif Search in Graphs: Application to Metabolic Networks

A 1.375-Approximation Algorithm for Sorting by Transpositions

New Bounds and Tractable Instances for the Transposition Distance

Comparing Tandem Repeats with Duplications and Excisions of Variable Degree

Faster Algorithms for Optimal Multiple Sequence Alignment Based on Pairwise Comparisons

Efficient Parameterized Algorithms for Biopolymer Structure-Sequence Alignment

Annual Index

Issue 3, July 2006

Issue 2, April 2006

Issue 1, January 2006

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 2

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) : Volume 1

Using Max Cut to Enhance Rooted Trees Consistency

Content Provider	ACM Digital Library
Author	Snir, Sagi Rao, Satish
Abstract	Supertree methods are used to construct a large tree over a large set of taxa from a set of small trees over overlapping subsets of the complete taxa set. Since accurate reconstruction methods are currently limited to a maximum of a few dozen taxa, the use of a supertree method in order to construct the tree of life is inevitable. Supertree methods are broadly divided according to the input trees: When the input trees are unrooted, the basic reconstruction unit is a quartet tree. In this case, the basic decision problem of whether there exists a tree that agrees with all quartets is NP-complete. On the other hand, when the input trees are rooted, the basic reconstruction unit is a rooted triplet and the above decision problem has a polynomial time algorithm. However, when there is no tree which agrees with all triplets, it would be desirable to find the tree that agrees with the maximum number of triplets. However, this optimization problem was shown to be NP-hard. Current heuristic approaches perform min cut on a graph representing the triplets inconsistency and return a tree that is guaranteed to satisfy some required properties. In this work, we present a different heuristic approach that guarantees the properties provided by the current methods and give experimental evidence that it significantly outperforms currently used methods. This method is based on a divide and conquer approach, where the min cut in the divide step is replaced by a max cut in a variant of the same graph. The latter is achieved by a lightweight semidefinite programming-like heuristic that leads to very fast running times.
Starting Page	323
Ending Page	333
Page Count	11
File Format	PDF
ISSN	15455963
DOI	10.1109/TCBB.2006.58
Volume Number	3
Issue Number	4
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-10-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Phylogenetic trees, supertrees, rooted triplets, semidefinite programming.
Content Type	Text
Resource Type	Article
Subject	Genetics Biotechnology Applied Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Using Max Cut to Enhance Rooted Trees Consistency

Using max cut to enhance rooted trees consistency (2006)

Computing a Smallest Multilabeled Phylogenetic Tree from Rooted Triplets

Drawing Rooted Phylogenetic Networks

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

Computing a Smallest Multilabeled Phylogenetic Tree from Rooted Triplets

Constructing Level-2 Phylogenetic Networks from Triplets

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

CBTH: A New Algorithm for Maximum Rooted Triplets Consistency Problem.

Using Max Cut to Enhance Rooted Trees Consistency

Similar Documents

Using Max Cut to Enhance Rooted Trees Consistency

Using max cut to enhance rooted trees consistency (2006)

Computing a Smallest Multilabeled Phylogenetic Tree from Rooted Triplets

Drawing Rooted Phylogenetic Networks

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

Computing a Smallest Multilabeled Phylogenetic Tree from Rooted Triplets

Constructing Level-2 Phylogenetic Networks from Triplets

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

CBTH: A New Algorithm for Maximum Rooted Triplets Consistency Problem.

Using Max Cut to Enhance Rooted Trees Consistency