Arrow Research search

Author name cluster

Tandy J. Warnow

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers
2 author rows

Possible papers

17

TCS Journal 2000 Journal Article

The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs

  • Hans L. Bodlaender
  • Michael R. Fellows
  • Michael T. Hallett
  • H.Todd Wareham
  • Tandy J. Warnow

In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has as a characteristic a uniform upper bound on the tree or path width of the graphs in “yes”-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for the complexity classes W[t] for all t∈ N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.

Details DOI

TCS Journal 1999 Journal Article

A few logs suffice to build (almost) all trees: Part II

  • Péter L. Erdös
  • Michael A. Steel
  • LászlóA. Székely
  • Tandy J. Warnow

Inferring evolutionary trees is an interesting and important problem in biology, but one that is computationally difficult as most associated optimization problems are NP-hard. Although many methods are provably statistically consistent (i. e. the probability of recovering the correct tree converges to 1 as the sequence length increases), the actual rate of convergence for different methods has not been well understood. In a recent paper we introduced a new method for reconstructing evolutionary trees called the dyadic closure method (DCM), and we showed that DCM has a very fast convergence rate. DCM runs in O(n 5 log n) time, where n is the number of sequences, and so, although polynomial, the computational requirements are potentially too large to be of use in practice. In this paper we present another tree reconstruction method, the witness-antiwitness method (WAM). WAM is faster than DCM, especially on random trees, and converges to the true tree topology at the same rate as DCM. We also compare WAM to other methods used to reconstruct trees, including Neighbor Joining (possibly the most popular method among molecular biologists), and new methods introduced in the computer science literature.

Details DOI

FOCS Conference 1990 Conference Paper

Inferring Evolutionary History from DNA Sequences (Extended Abstract)

  • Sampath Kannan
  • Tandy J. Warnow

Two related problems are considered. The first is determining whether it is possible to triangulate a vertex-colored graph without introducing edges between vertices of the same color. This is related to a fundamental problem for geneticists, that of using character state information to construct evolutionary trees. The polynomial equivalence of these problems is demonstrated. An important subproblem arises when the characters are based on DNA sequences. Such characters assume up to four states. An O(n/sup 2/k) algorithm, where n is the number of species and k is the number of characters, is presented for this case. >

Details
v2026.09.13