Evaluation of BLAST-based edge-weighting metrics used for homology inference with the Markov Clustering algorithm

Simple item page
dc.contributor.authorGibbons, Theodore R.
dc.contributor.authorMount, Stephen M.
dc.contributor.authorCooper, Endymion D.
dc.contributor.authorDelwiche, Charles F.
dc.date.accessioned2021-08-17T18:19:45Z
dc.date.available2021-08-17T18:19:45Z
dc.date.issued2015-07-10
dc.description.abstractClustering protein sequences according to inferred homology is a fundamental step in the analysis of many large data sets. Since the publication of the Markov Clustering (MCL) algorithm in 2002, it has been the centerpiece of several popular applications. Each of these approaches generates an undirected graph that represents sequences as nodes connected to each other by edges weighted with a BLAST-based metric. MCL is then used to infer clusters of homologous proteins by analyzing these graphs. The various approaches differ only by how they weight the edges, yet there has been very little direct examination of the relative performance of alternative edge-weighting metrics. This study compares the performance of four BLAST-based edge-weighting metrics: the bit score, bit score ratio (BSR), bit score over anchored length (BAL), and negative common log of the expectation value (NLE). Performance is tested using the Extended CEGMA KOGs (ECK) database, which we introduce here. All metrics performed similarly when analyzing full-length sequences, but dramatic differences emerged as progressively larger fractions of the test sequences were split into fragments. The BSR and BAL successfully rescued subsets of clusters by strengthening certain types of alignments between fragmented sequences, but also shifted the largest correct scores down near the range of scores generated from spurious alignments. This penalty outweighed the benefits in most test cases, and was greatly exacerbated by increasing the MCL inflation parameter, making these metrics less robust than the bit score or the more popular NLE. Notably, the bit score performed as well or better than the other three metrics in all scenarios. The results provide a strong case for use of the bit score, which appears to offer equivalent or superior performance to the more popular NLE. The insight that MCL-based clustering methods can be improved using a more tractable edge-weighting metric will greatly simplify future implementations. We demonstrate this with our own minimalist Python implementation: Porthos, which uses only standard libraries and can process a graph with 25 m + edges connecting the 60 k + KOG sequences in half a minute using less than half a gigabyte of memory.en_US
dc.description.urihttps://doi.org/10.1186/s12859-015-0625-x
dc.description.urihttps://doi.org/10.1186/s12859-015-0690-1
dc.identifierhttps://doi.org/10.13016/miwn-l7oi
dc.identifier.citationGibbons, T.R., Mount, S.M., Cooper, E.D. et al. Evaluation of BLAST-based edge-weighting metrics used for homology inference with the Markov Clustering algorithm. BMC Bioinformatics 16, 218 (2015).en_US
dc.identifier.urihttp://hdl.handle.net/1903/27623
dc.language.isoen_USen_US
dc.publisherSpringer Natureen_US
dc.relation.isAvailableAtCell Biology & Molecular Geneticsen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtCollege of Computer, Mathematical & Natural Sciencesen_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us
dc.subjectMCLen_US
dc.subjectProtein clusteringen_US
dc.subjectSequence clusteringen_US
dc.subjectHomology predictionen_US
dc.subjectGraphen_US
dc.subjectGenomicsen_US
dc.subjectBioinformaticsen_US
dc.subjectTranscriptomicsen_US
dc.subjectShort-read sequencingen_US
dc.subjectHigh-throughput sequencingen_US
dc.titleEvaluation of BLAST-based edge-weighting metrics used for homology inference with the Markov Clustering algorithmen_US
dc.typeArticleen_US

Files

Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
s12859-015-0625-x.pdf
Size:
4.46 MB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
s12859-015-0690-1.pdf
Size:
381.55 KB
Format:
Adobe Portable Document Format
Description:
Erratum
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.57 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Cell Biology & Molecular Genetics Research Works