LZ Complexity Distance of DNA Sequences and Its Application in Phylogenetic Tree Reconstruction

DNA sequences can be treated as finite-length symbol strings over a four-letter alphabet (A, C, T, G). As a universal and computable complexity measure, LZ complexity is valid to describe the complexity of DNA sequences. In this study, a concept of conditional LZ complexity between two sequences is proposed according to the principle of LZ complexity measure. An LZ complexity distance metric between two nonnull sequences is defined by utilizing conditional LZ complexity. Based on LZ complexity distance, a phylogenetic tree of 26 species of placental mammals (Eutheria) with three outgroup species was reconstructed from their complete mitochondrial genomes. On the debate that which two of the three main groups of placental mammals, namely Primates, Ferungulates, and Rodents, are more closely related, the phylogenetic tree reconstructed based on LZ complexity distance supports the suggestion that Primates and Ferungulates are more closely related.

• Publication year

  2016

• Venue

  Genomics, Proteomics & Bioinformatics

• Publication date

  2016-11-28

• Fields of study

  Biology, Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1016/S1672-0229(05)03028-7PMID 16689687PMCID 5172548
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Alignment-free sequence comparison-a review

  2003cited by this paper
• An information-based sequence distance and its application to whole mitochondrial genome phylogeny

  2001cited by this paper
• DNA Data Compression in the Post Genome Era

  2001cited by this paper
• Where do rodents fit? Evidence from the complete mitochondrial genome of Sciurus vulgaris.

  2000cited by this paper
• A compression algorithm for DNA sequences and its applications in genome comparison

  2000cited by this paper
• Bioinformatics Methods and Protocols

  1999cited by this paper
• Conflict Among Individual Mitochondrial Proteins in Resolving the Phylogeny of Eutherian Orders

  1998cited by this paper
• Complete mitochondrial DNA sequence of the fat dormouse, Glis glis: further evidence of rodent paraphyly.

  1998cited by this paper
• Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))

  1997cited by this paper
• Are Guinea Pigs Rodents? The Importance of Adequate Models in Molecular Phylogenetics

  1997cited by this paper
• The complete mitochondrial genome of the wallaroo (Macropus robustus) and the phylogenetic relationship among Monotremata, Marsupialia, and Eutheria.

  1997cited by this paper
• Phylogenetic position of guinea pigs revisited.

  1997cited by this paper
• TreeView: an application to display phylogenetic trees on personal computers

  1996influential reference
• Mammalian phylogeny inferred from multiple protein data.

  1994cited by this paper
• The neighbor-joining method : A new method for reconstructing phylogenetic trees

  1987cited by this paper
• The neighbor-joining method: a new method for reconstructing phylogenetic trees.

  1987influential reference
• Easily calculable measure for the complexity of spatiotemporal patterns.

  1987cited by this paper
• On the Complexity of Finite Sequences

  1976cited by this paper

• A unique approach for protein secondary structure comparison under TOPS representation

  2024cites this paper
• Compression-Complexity Measures for Analysis and Classification of Coronaviruses

  2022cites this paper
• Reconstrução de Árvores Filogenéticas a partir de mtDNA usando o Algoritmo SEQUITUR

  2021cites this paper
• Automatic Identification of SARS Coronavirus using Compression-Complexity Measures

  2020cites this paper
• The Lempel–Ziv measure based pedigree map to detect and evaluate correlation between aero-engine gas path system variables

  2019cites this paper
• DNA Sequence Classification: It’s Easier Than You Think: An open-source k-mer based machine learning tool for fast and accurate classification of a variety of genomic datasets

  2018cites this paper
• Pattern recognition and probabilistic measures in alignment-free sequence analysis

  2014cites this paper
• Phylogenetic Analysis of Protein Sequences Based on Distribution of Length About Common Substring

  2011cites this paper
• Phylogenetic Analysis of Protein Sequences Based on Conditional LZ Complexity

  2010cites this paper
• [A new alignment-free sequence analysis based on the distribution of K-tuple].

  2010cites this paper
• Efficiency of financial markets and algorithmic complexity

  2010cites this paper
• A complexity-based measure and its application to phylogenetic analysis

  2008cites this paper
• Algorithmic complexity theory and the relative efficiency of financial markets

  2008cites this paper