Long-read sequencing of transcripts with Pacific Biosciences (PacBio) Iso-Seq and Oxford Nanopore Technologies has proven to be central to the study of complex isoform landscapes in many organisms. However, current de novo transcript reconstruction algorithms from long-read data are limited, leaving the potential of these technologies unfulfilled. A common bottleneck is the dearth of scalable and accurate algorithms for clustering long reads according to their gene family of origin. To address this challenge, we develop isONclust, a clustering algorithm that is greedy (to scale) and makes use of quality values (to handle variable error rates). We test isONclust on three simulated and five biological data sets, across a breadth of organisms, technologies, and read depths. Our results demonstrate that isONclust is a substantial improvement over previous approaches, both in terms of overall accuracy and/or scalability to large data sets.
Get full access to this article
View all access options for this article.
References
1.
SahlinK., and MedvedevP.2019. isONclust: De novo clustering of long transcript reads into genes. GitHub repository, https://github.com/ksahlin/isONclust
2.
AlankoJ., CunialF., BelazzouguiD., et al.2017. A framework for space-efficient read clustering in metagenomic samples. BMC Bioinformatics, 18, 59.
3.
AuK.F., UnderwoodJ.G., LeeL., et al.2012. Improving PacBio long read accuracy by short read alignment. PLoS One, 7, e46679.
4.
BaoE., JiangT., KaloshianI., et al.2011. SEED: Efficient clustering of next-generation sequences. Bioinformatics, 27, 2502–2509.
5.
BevilacquaV., PietroleonardoN., GianninoE.I., et al.2014. EasyCluster2: An improved tool for clustering and assembling long transcriptome reads. BMC Bioinformatics, 15, S7.
6.
BurkeJ., DavisonD., and HideW.1999. d2_cluster: A validated method for clustering EST and full-length cDNA sequences. Genome Res. 9, 1135.
7.
ByrneA., BeaudinA.E., OlsenH.E., et al.2017. Nanopore long-read RNAseq reveals widespread transcriptional variation among the surface receptors of individual B cells. Nat. Commun. 8, 16027.
8.
ChongZ., RuanJ., and WuC.-I.2012. Rainbow: An integrated tool for efficient clustering and assembling rad-seq reads.Bioinformatics 28, 2732–2737.
9.
ChristoffelsA., GelderA.V., GreylingG., et al.2001. STACK: Sequence tag alignment and consensus knowledgebase. Nucleic Acids Res. 29, 234–238.
10.
CominM., LeoniA., and SchimdM.2015. Clustering of reads with alignment-free measures and quality values. Algorithms Mol. Biol. 10, 4.
11.
DailyJ.2016. Parasail: SIMD C library for global, semi-global, and local pairwise sequence alignments. BMC Bioinformatics, 17, 81.
12.
DavidsonN.M., and OshlackA.2014. Corset: Enabling differential gene expression analysis for de novoassembled transcriptomes. Genome Biol. 15, 410.
13.
DostB., WuC., SuA., et al.2011. TCLUST: A fast method for clustering genome-scale expression data. IEEE/ACM Trans. Comput. Biol. Bioinformatics, 8, 808–818.
14.
EdgarR.C.2010. Search and clustering orders of magnitude faster than BLAST. Bioinformatics, 26, 2460–2461.
15.
FuL., NiuB., ZhuZ., et al.2012. CD-HIT: Accelerated for clustering the next-generation sequencing data. Bioinformatics, 28, 3150–3152.
16.
GhodsiM., LiuB., and PopM.2011. DNACLUST: Accurate and efficient clustering of phylogenetic marker genes. BMC Bioinformatics, 12, 271.
17.
GordonS.P., TsengE., SalamovA., et al.2015. Widespread polycistronic transcripts in fungi revealed by single-molecule mRNA sequencing. PLoS One, 10, e0132628.
18.
HoangN.V., FurtadoA., MasonP.J., et al.2017. A survey of the complex transcriptome from the highly polyploid sugarcane genome using full-length isoform sequencing and de novo assembly from short read sequencing. BMC Genomics, 18, 395.
19.
HubertL., and ArabieP.1985. Comparing partitions. J. Classif. 2, 193–218.
20.
JamesB.T., LuczakB.B., and GirgisH.Z.2018. MeShClust: An intelligent tool for clustering DNA sequences. Nucleic Acids Res. 46, e83.
21.
KorlachJ., GedmanG., KinganS.B., et al.2017. De novo PacBio long-read and phased avian genome assemblies correct and add to reference genes generated with intermediate and short reads. Gigascience, 6, gix085.
22.
KrishnakumarR., SinhaA., BirdS.W., et al.2018. Systematic and stochastic influences on the performance of the MinION nanopore sequencer across a range of nucleotide bias. Sci. Rep.s, 8, 3159.
23.
KuoR.I., TsengE., EoryL., et al.2017. Normalized long read rna sequencing in chicken reveals transcriptome complexity similar to human. BMC Genomics, 18, 323.
24.
LiH.2018. Minimap2: Pairwise alignment for nucleotide sequences.Bioinformatics 1:7.
25.
LiJ., Harata-LeeY., DentonM.D., et al.2017. Long read reference genome-free reconstruction of a full-length transcriptome from astragalus membranaceus reveals transcript variants involved in bioactive compound biosynthesis. Cell Discov. 3, 17031.
26.
LiW., and GodzikA.2006. Cd-hit: A fast program for clustering and comparing large sets of protein or nucleotide sequences. Bioinformatics, 22, 1658–1659.
27.
LiuX., MeiW., SoltisP.S., et al.2017. Detecting alternatively spliced transcript isoforms from single-molecule long-read sequences without a reference genome. Mol. Ecol. Resour. 17, 1243–1256.
MalikL., AlmodaresiF., and PatroR.2018. Grouper: Graph-based clustering and annotation for improved de novo transcriptome analysis. Bioinformatics, 1, 8.
30.
MarchetC., LecompteL., SilvaC.D., et al.2019. De novo clustering of long reads by gene from transcriptomics data. Nucleic Acids Res. 47, e2.
31.
NattestadM., GoodwinS., NgK., et al.2018. Complex rearrangements and oncogene amplifications revealed by long-read dna and rna sequencing of a breast cancer cell line. Genome Res. 28, 1126–1135.
32.
OndovB.D., TreangenT.J., MelstedP., et al.2016. Mash: Fast genome and metagenome distance estimation using MinHash. Genome Biol. 17, 132.
33.
OrabiB., ErhanE., McConeghyB., et al.2019. Alignment-free clustering of UMI tagged DNA molecules. Bioinformatics, 35, 1829–1836.
34.
PaccanaroA., CasbonJ. A., and SaqiM. A.2006. Spectral clustering of protein sequences. Nucleic Acids Res. 34, 1571–1580.
35.
RobertsM., HayesW., HuntB. R., et al.2004. Reducing storage requirements for biological sequence comparison. Bioinformatics, 20, 3363–3369.
36.
RosenbergA., and HirschbergJ.2007. V-measure: A conditional entropy-based external cluster evaluation measure. Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). Prague, Czech Republic.
37.
SahlinK., and MedvedevP.2019. Experimental details appendix to “De novo clustering of long-read transcriptome data using a greedy, quality-value based algorithm.” Available at: https://github.com/ksahlin/isONclust/wiki/Paper-Appendix Accessed February12, 2020.
38.
SahlinK., TomaszkiewiczM., MakovaK.D., et al.2018. Deciphering highly similar multigene family transcripts from iso-seq data with isocon.Nat. Commun. 9, 4601.
39.
ShimizuK., and TsudaK.2010. SlideSort: All pairs similarity search for short reads. Bioinformatics, 27, 464–470.
40.
SolovyovA., and LipkinW.I.2013. Centroid based clustering of high throughput sequencing reads based on n-mer counts. BMC Bioinformatics, 14, 268.
41.
SteineggerM., and SödingJ.2017. MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets. Nat. Biotechnol. 35, 1026–1028.
42.
SteineggerM., and SödingJ.2018. Clustering huge protein sequence sets in linear time. Nat. Commun. 9, 2542.
43.
StöckerB.K., KösterJ., and RahmannS.2016. SimLoRD: Simulation of long read data. Bioinformatics, 32, 2704–2706.
44.
TombáczD., CsabaiZ., SzűcsA., et al.2017. Long-read isoform sequencing reveals a hidden complexity of the transcriptional landscape of herpes simplex virus type 1. Front. Microbiol. 8, 1079.
TsengE.2018. Cogent: Coding genome reconstruction using iso-seq data. Available at: https://github.com/Magdoll/Cogent. Accessed February12, 2020.
47.
TsengE., TangH.-T., AlOlabyR. R., et al.2017. Altered expression of the fmr1 splicing variants landscape in premutation carriers. Biochim. Biophys. Acta, 1860, 1117–1126.
48.
WorkmanR.E., MyrkaA.M., WongG.W., et al.2018. Single-molecule, full-length transcript sequencing provides insight into the extreme metabolism of the ruby-throated hummingbird archilochus colubris. Gigascience, 7, giy009.
49.
ZoritaE., CuscoP., and FilionG.J.2015. Starcode: Sequence clustering based on all-pairs search. Bioinformatics, 31, 1913–1919.
