Efficient large-scale protein sequence comparison and gene matching to identify orthologs and co-orthologs
Open Access
- 29 December 2011
- journal article
- research article
- Published by Oxford University Press (OUP) in Nucleic Acids Research
- Vol. 40 (6) , e44
Abstract
Broadly, computational approaches for ortholog assignment is a three steps process: (i) identify all putative homologs between the genomes, (ii) identify gene anchors and (iii) link anchors to identify best gene matches given their order and context. In this article, we engineer two methods to improve two important aspects of this pipeline [specifically steps (ii) and (iii)]. First, computing sequence similarity data [step (i)] is a computationally intensive task for large sequence sets, creating a bottleneck in the ortholog assignment pipeline. We have designed a fast and highly scalable sort-join method (afree) based on k -mer counts to rapidly compare all pairs of sequences in a large protein sequence set to identify putative homologs. Second, availability of complex genomes containing large gene families with prevalence of complex evolutionary events, such as duplications, has made the task of assigning orthologs and co-orthologs difficult. Here, we have developed an iterative graph matching strategy where at each iteration the best gene assignments are identified resulting in a set of orthologs and co-orthologs. We find that the afree algorithm is faster than existing methods and maintains high accuracy in identifying similar genes. The iterative graph matching strategy also showed high accuracy in identifying complex gene relationships. Standalone afree available from http://vbc.med.monash.edu.au/∼kmahmood/afree . EGM2, complete ortholog assignment pipeline (including afree and the iterative graph matching method) available from http://vbc.med.monash.edu.au/∼kmahmood/EGM2 .Keywords
This publication has 42 references indexed in Scilit:
- Search and clustering orders of magnitude faster than BLASTBioinformatics, 2010
- An alignment-free method to identify candidate orthologous enhancers in multiple Drosophila genomesBioinformatics, 2010
- Alignment-free local structural search by writhe decompositionBioinformatics, 2010
- Finding related sentence pairs in MEDLINEInformation Retrieval Journal, 2010
- Finding regulatory DNA motifs using alignment-free evolutionary conservation informationNucleic Acids Research, 2010
- Whole-proteome phylogeny of prokaryotes by feature frequency profiles: An alignment-free method with optimal feature resolutionProceedings of the National Academy of Sciences, 2009
- Ensembl 2008Nucleic Acids Research, 2007
- OrthoDB: the hierarchical catalog of eukaryotic orthologsNucleic Acids Research, 2007
- Comparative genomics using Fugu reveals insights into regulatory subfunctionalizationGenome Biology, 2007
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997