phylogenetic-tree-cpp

A C++ tool for constructing phylogenetic trees from biological sequence data using four distance-based algorithms. Takes DNA/protein sequences in FASTA format, computes evolutionary distances, and outputs trees in Newick format.

• College: CVR College of Engineering, Hyderabad
• Department: Computer Science and Engineering
• Academic Year: 2025–2026
• Guide: Dr. C. Ramesh, Professor & Associate Dean, Dept. of CSE

Four tree construction algorithms:

• Neighbor-Joining (NJ): Fast, widely used, O(n³) complexity
• Fitch-Margoliash (FM): Weighted least squares optimization, accurate branch lengths
• UPGMA: Ultrametric trees, assumes molecular clock, O(n²) complexity
• Minimum Evolution (ME): Minimizes total branch length, good for varying evolutionary rates

Three distance calculation methods:

• Fractional k-mer count (default) — normalized k-mer frequency differences
• Mahalanobis distance (-m) — accounts for k-mer correlation
• Cosine distance (-c) — compares k-mer profile vectors

g++ -o phylogenetic-tree-cpp main.cpp tree.cpp neighbor_joining.cpp fitch_margoliash.cpp upgma.cpp minimum_evolution.cpp tree_io.cpp operations.cpp eval.cpp -std=c++11

./phylogenetic-tree-cpp <input.fasta> [options]

# Basic run — Neighbor-Joining
./phylogenetic-tree-cpp test.fasta

# UPGMA algorithm
./phylogenetic-tree-cpp test.fasta -upgma

# Fitch-Margoliash algorithm
./phylogenetic-tree-cpp test.fasta -fm

# Minimum Evolution algorithm
./phylogenetic-tree-cpp test.fasta -me

# Mahalanobis distance with k-mer length 6
./phylogenetic-tree-cpp Orthologs.fasta -m -k 6

# Cosine distance with verbose output
./phylogenetic-tree-cpp nucOrth.fasta -c -v

The program generates output.txt in Newick format, for example:

(Pseudomonas:1.109149, Stenotrophomonas:1.109149);

This can be visualized using:

• FigTree — desktop application
• iTOL (Interactive Tree of Life) — online at itol.embl.de

phylogenetic-tree-cpp/
├── main.cpp                  # Entry point, argument parsing
├── tree.hpp                  # Header — structs and declarations
├── tree.cpp                  # Tree class implementation
├── neighbor_joining.cpp      # NJ algorithm
├── fitch_margoliash.cpp      # FM algorithm
├── upgma.cpp                 # UPGMA algorithm
├── minimum_evolution.cpp     # ME algorithm
├── operations.cpp            # K-mer distance calculations
├── tree_io.cpp               # FASTA reading, file writing
├── eval.cpp                  # Bootstrap analysis
├── me.cpp                    # ME standalone demo
├── test.fasta                # Sample input (2 sequences)
├── Orthologs.fasta           # Sample input (5 sequences)
├── Orthologs2.fasta          # Sample input (5 sequences)
├── nucOrth.fasta             # Sample input (5 sequences)
└── output.txt                # Sample output (Newick tree)

Input FASTA file
      ↓
Read & parse DNA sequences
      ↓
Count k-mer frequencies
      ↓
Compute pairwise distance matrix
      ↓
Run selected algorithm (NJ / UPGMA / FM / ME)
      ↓
Output Newick tree → output.txt

• R. Himabindhu — 23B81A05CN
• J. Nimitha — 23B81A05CZ
• K. Sai Hruthik — 23B81A05DJ — GitHub

• Saitou & Nei (1987) — The Neighbor-Joining Method, Molecular Biology and Evolution
• Fitch & Margoliash (1967) — Construction of Phylogenetic Trees, Science
• Sneath & Sokal (1973) — Numerical Taxonomy