Evolutionary profiles from the QR factorization of multiple sequence alignments

Anurag Sethi, Patrick O'Donoghue, Zaida Luthey-Schulten

Research output: Contribution to journalArticlepeer-review


We present an algorithm to generate complete evolutionary profiles that represent the topology of the molecular phylogenetic tree of the homologous group. The method, based on the multi-dimensional QR factorization of numerically encoded multiple sequence alignments, removes redundancy from the alignments and orders the protein sequences by increasing linear dependence, resulting in the identification of a minimal basis set of sequences that spans the evolutionary space of the homologous group of proteins. We observe a general trend that these smaller, more evolutionarily balanced profiles have comparable and, in many cases, better performance in database searches than conventional profiles containing hundreds of sequences, constructed in an iterative and computationally intensive procedure. For more diverse families or superfamilies, with sequence identity <30%, structural alignments, based purely on the geometry of the protein structures, provide better alignments than pure sequence-based methods. Merging the structure and sequence information allows the construction of accurate profiles for distantly related groups. These structure-based profiles outperformed other sequence-based methods for finding distant homologs and were used to identify a putative class II cysteinyl-tRNA synthetase (CysRS) in several archaea that eluded previous annotation studies. Phylogenetic analysis showed the putative class II CysRSs to be a monophyletic group and homology modeling revealed a constellation of active site residues similar to that in the known class I CysRS.

Original languageEnglish (US)
Pages (from-to)4045-4050
Number of pages6
JournalProceedings of the National Academy of Sciences of the United States of America
Issue number11
StatePublished - Mar 15 2005


  • Archaeal cysteinyl-tRNA synthetase
  • Gene annotation
  • Lipocalin
  • Superfamily
  • Triosephosphate isomerase superfamily

ASJC Scopus subject areas

  • General


Dive into the research topics of 'Evolutionary profiles from the QR factorization of multiple sequence alignments'. Together they form a unique fingerprint.

Cite this