Welcome to the UPF Digital Repository

Starcode: sequence clustering based on all-pairs search

Show simple item record

dc.contributor.author Zorita, Eduard
dc.contributor.author Cuscó Pons, Pol, 1987-
dc.contributor.author Filion, Guillaume
dc.date.accessioned 2015-11-11T18:44:57Z
dc.date.available 2015-11-11T18:44:57Z
dc.date.issued 2015
dc.identifier.citation Zorita E, Cuscó P, Filion GJ. Starcode: sequence clustering based on all-pairs search. Bioinformatics. 2015;31(12):1913-9. DOI: 10.1093/bioinformatics/btv053
dc.identifier.issn 1367-4803
dc.identifier.uri http://hdl.handle.net/10230/25055
dc.description.abstract Motivation: The increasing throughput of sequencing technologies offers new applications and challenges for computational biology. In many of those applications, sequencing errors need to be/ncorrected. This is particularly important when sequencing reads from an unknown reference such as random DNA barcodes. In this case, error correction can be done by performing a pairwise comparison/nof all the barcodes, which is a computationally complex problem. Results: Here, we address this challenge and describe an exact algorithm to determine which pairs of sequences lie within a given Levenshtein distance. For error correction or redundancy reduction purposes, matched pairs are then merged into clusters of similar sequences. The efficiency of starcode is attributable to the poucet search, a novel implementation of the Needleman–Wunsch algorithm performed on the nodes of a trie. On the task of matching random barcodes, starcode outperforms sequence clustering algorithms in both speed and precision. Availability and implementation: The C source code is available at http://github.com/gui11aume/starcode.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Oxford University Press
dc.relation.ispartof Bioinformatics. 2015;31(12):1913-9
dc.rights © The Author 2014. Published by Oxford University Press. This is an open access article published under a Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
dc.rights.uri http://creativecommons.org/licenses/by-nc/4.0/
dc.subject.other Bioinformàtica
dc.subject.other Biologia computacional
dc.title Starcode: sequence clustering based on all-pairs search
dc.type info:eu-repo/semantics/article
dc.identifier.doi http://dx.doi.org/10.1093/bioinformatics/btv053
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/publishedVersion

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

In collaboration with Compliant to Partaking