Phylogenomic analyses are essential for understanding evolutionary relationships and are increasingly important for crop improvement. However, traditional alignment-based methods become computationally demanding with large plant genomes, such as tomato. This paper presents a scalable and alignment-free approach for reconstructing tomato phylogeny using Normalized Compression Distance (NCD). Due to the large size of tomato genomes, we introduce a novel segmentation strategy, dividing the genomes into 70 segments. NCD is applied to each segment to generate distance matrices, which are then averaged to create a final matrix representing the whole-genome distances. A phylogenetic tree is constructed from this final matrix and validated against established relationships in the tomato clade. Our findings demonstrate the potential of NCD with segmentation as a computationally efficient approach for inferring phylogeny from large plant genomes. This method offers an alternative to traditional alignment-based methods, opening avenues for exploring evolutionary relationships in other crops with complex and substantial genomes.

We compare the accuracy of the Normalized Compress Distance (NCD) techniques for building phylogenetic trees from molecular data with the more widely used techniques of Neighbor joining with p value and Bayesian inference. The NCD algorithm is a distance-based alignment-free method and as such takes unaligned sequence data as input and outputs a distance matrix. The matrix is given as input to FastME, which outputs a tree in Newick format. Every step of this process require minimal processing and as such provides fast execution times along with minimal restrictions on input data.Motivation: Our work was motivated by the 2004 paper Clustring by Compression [1] by Cilibrasi and Vitanyi. They analyze sets of data from linguistics, literature, and music to demonstrate how the NCD method aids classification. In that paper, they also used NCD to build a phylogeny on a set of 24 whole mammalian mitochondrial genomes. They used the bzip2 compressor, which yielded a distance matrix, and then generated a tree from that using a new quartet tree method they developed.

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNP NP functions are not computable in polynomial-time with an NP oracle.

The class NP k V consists of those partial, multivalued functions that can be computed by a nondeterministic, polynomial time-bounded transducer that has at most k distinct values on any input. We define the output-multiplicity hierarchy to consist of the collection of classes NP k V for all positive integers k ≥ 1. In this paper we investigate the strictness of the output-multiplicity hierarchy and establish three main results pertaining to this: 1. 1. If for any k > 1, the class NP k V collapses into the class NP( k − 1)V, then the polynomial hierarchy collapses to Σ 2 P . 2. 2. If the converse of the above result is true, then any proof of this converse cannot relativize. We exhibit an oracle relative to which the polynomial hierarchy collapses to P NP , but the output-multiplicity hierarchy is strict. 3. 3. Relative to a random oracle, the output-multiplicity hierarchy is strict. This result is in contrast to the still open problem of the strictness of the polynomial hierarchy relative to a random oracle. In introducing the technique for the third result we prove a related result of interest: relative to a random oracle UP ≠ NP.

We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: One can find accepting paths of nondeterministic polynomial-time Turing machines that accept /spl Sigma/*. Every total multivalued nondeterministic function has a polynomial-time computable refinement. One can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. One can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse, path, etc.