@article {472, title = {Fast inexact mapping using advanced tree exploration on backward search methods.}, journal = {BMC Bioinformatics}, volume = {16}, year = {2015}, month = {2015 Jan 28}, pages = {18}, abstract = {

BACKGROUND: Short sequence mapping methods for Next Generation Sequencing consist on a combination of seeding techniques followed by local alignment based on dynamic programming approaches. Most seeding algorithms are based on backward search alignment, using the Burrows Wheeler Transform, the Ferragina and Manzini Index or Suffix Arrays. All these backward search algorithms have excellent performance, but their computational cost highly increases when allowing errors. In this paper, we discuss an inexact mapping algorithm based on pruning strategies for search tree exploration over genomic data.

RESULTS: The proposed algorithm achieves a 13x speed-up over similar algorithms when allowing 6 base errors, including insertions, deletions and mismatches. This algorithm can deal with 400 bps reads with up to 9 errors in a high quality Illumina dataset. In this example, the algorithm works as a preprocessor that reduces by 55\% the number of reads to be aligned. Depending on the aligner the overall execution time is reduced between 20-40\%.

CONCLUSIONS: Although not intended as a complete sequence mapping tool, the proposed algorithm could be used as a preprocessing step to modern sequence mappers. This step significantly reduces the number reads to be aligned, accelerating overall alignment time. Furthermore, this algorithm could be used for accelerating the seeding step of already available sequence mappers. In addition, an out-of-core index has been implemented for working with large genomes on systems without expensive memory configurations.

}, keywords = {Algorithms, Genome, Human, Genomics, High-Throughput Nucleotide Sequencing, Humans, Sequence Alignment, Sequence Analysis, DNA, Software}, issn = {1471-2105}, doi = {10.1186/s12859-014-0438-3}, author = {Salavert, Jos{\'e} and Tom{\'a}s, Andr{\'e}s and T{\'a}rraga, Joaqu{\'\i}n and Medina, Ignacio and Dopazo, Joaquin and Blanquer, Ignacio} } @article {522, title = {Using GPUs for the exact alignment of short-read genetic sequences by means of the Burrows-Wheeler transform.}, journal = {IEEE/ACM Trans Comput Biol Bioinform}, volume = {9}, year = {2012}, month = {2012 Jul-Aug}, pages = {1245-56}, abstract = {

General Purpose Graphic Processing Units (GPGPUs) constitute an inexpensive resource for computing-intensive applications that could exploit an intrinsic fine-grain parallelism. This paper presents the design and implementation in GPGPUs of an exact alignment tool for nucleotide sequences based on the Burrows-Wheeler Transform. We compare this algorithm with state-of-the-art implementations of the same algorithm over standard CPUs, and considering the same conditions in terms of I/O. Excluding disk transfers, the implementation of the algorithm in GPUs shows a speedup larger than 12, when compared to CPU execution. This implementation exploits the parallelism by concurrently searching different sequences on the same reference search tree, maximizing memory locality and ensuring a symmetric access to the data. The paper describes the behavior of the algorithm in GPU, showing a good scalability in the performance, only limited by the size of the GPU inner memory.

}, keywords = {Algorithms, Animals, Computational Biology, Computer Graphics, Data Compression, Drosophila melanogaster, Genes, Insect, Image Processing, Computer-Assisted, Models, Genetic, Sequence Alignment, Sequence Analysis, DNA}, issn = {1557-9964}, doi = {10.1109/TCBB.2012.49}, author = {Salavert Torres, Jose and Blanquer Espert, Ignacio and Dom{\'\i}nguez, Andr{\'e}s Tom{\'a}s and Hern{\'a}ndez Garc{\'\i}a, Vicente and Medina Castell{\'o}, Ignacio and T{\'a}rraga Gim{\'e}nez, Joaqu{\'\i}n and Dopazo Bl{\'a}zquez, Joaqu{\'\i}n} } @article {539, title = {Phylemon 2.0: a suite of web-tools for molecular evolution, phylogenetics, phylogenomics and hypotheses testing.}, journal = {Nucleic Acids Res}, volume = {39}, year = {2011}, month = {2011 Jul}, pages = {W470-4}, abstract = {

Phylemon 2.0 is a new release of the suite of web tools for molecular evolution, phylogenetics, phylogenomics and hypotheses testing. It has been designed as a response to the increasing demand of molecular sequence analyses for experts and non-expert users. Phylemon 2.0 has several unique features that differentiates it from other similar web resources: (i) it offers an integrated environment that enables evolutionary analyses, format conversion, file storage and edition of results; (ii) it suggests further analyses, thereby guiding the users through the web server; and (iii) it allows users to design and save phylogenetic pipelines to be used over multiple genes (phylogenomics). Altogether, Phylemon 2.0 integrates a suite of 30 tools covering sequence alignment reconstruction and trimming; tree reconstruction, visualization and manipulation; and evolutionary hypotheses testing.

}, keywords = {Evolution, Molecular, Genomics, Internet, Phylogeny, Sequence Alignment, Software}, issn = {1362-4962}, doi = {10.1093/nar/gkr408}, author = {S{\'a}nchez, Rub{\'e}n and Serra, Fran{\c c}ois and T{\'a}rraga, Joaqu{\'\i}n and Medina, Ignacio and Carbonell, Jos{\'e} and Pulido, Luis and De Maria, Alejandro and Capella-Gut{\'\i}errez, Salvador and Huerta-Cepas, Jaime and Gabald{\'o}n, Toni and Dopazo, Joaquin and Dopazo, Hern{\'a}n} } @article {598, title = {PhylomeDB: a database for genome-wide collections of gene phylogenies.}, journal = {Nucleic Acids Res}, volume = {36}, year = {2008}, month = {2008 Jan}, pages = {D491-6}, abstract = {

The complete collection of evolutionary histories of all genes in a genome, also known as phylome, constitutes a valuable source of information. The reconstruction of phylomes has been previously prevented by large demands of time and computer power, but is now feasible thanks to recent developments in computers and algorithms. To provide a publicly available repository of complete phylomes that allows researchers to access and store large-scale phylogenomic analyses, we have developed PhylomeDB. PhylomeDB is a database of complete phylomes derived for different genomes within a specific taxonomic range. All phylomes in the database are built using a high-quality phylogenetic pipeline that includes evolutionary model testing and alignment trimming phases. For each genome, PhylomeDB provides the alignments, phylogentic trees and tree-based orthology predictions for every single encoded protein. The current version of PhylomeDB includes the phylomes of Human, the yeast Saccharomyces cerevisiae and the bacterium Escherichia coli, comprising a total of 32 289 seed sequences with their corresponding alignments and 172 324 phylogenetic trees. PhylomeDB can be publicly accessed at http://phylomedb.bioinfo.cipf.es.

}, keywords = {Base Sequence, Escherichia coli, Genes, Genomics, History, Ancient, Humans, Phylogeny, Proteins, Saccharomyces cerevisiae, Sequence Alignment}, issn = {1362-4962}, doi = {10.1093/nar/gkm899}, author = {Huerta-Cepas, Jaime and Bueno, Anibal and Dopazo, Joaquin and Gabald{\'o}n, Toni} } @article {603, title = {DBAli tools: mining the protein structure space.}, journal = {Nucleic Acids Res}, volume = {35}, year = {2007}, month = {2007 Jul}, pages = {W393-7}, abstract = {

The DBAli tools use a comprehensive set of structural alignments in the DBAli database to leverage the structural information deposited in the Protein Data Bank (PDB). These tools include (i) the DBAlit program that allows users to input the 3D coordinates of a protein structure for comparison by MAMMOTH against all chains in the PDB; (ii) the AnnoLite and AnnoLyze programs that annotate a target structure based on its stored relationships to other structures; (iii) the ModClus program that clusters structures by sequence and structure similarities; (iv) the ModDom program that identifies domains as recurrent structural fragments and (v) an implementation of the COMPARER method in the SALIGN command in MODELLER that creates a multiple structure alignment for a set of related protein structures. Thus, the DBAli tools, which are freely accessible via the World Wide Web at http://salilab.org/DBAli/, allow users to mine the protein structure space by establishing relationships between protein structures and their functions.

}, keywords = {Algorithms, Amino Acid Sequence, Computational Biology, Data Interpretation, Statistical, Databases, Protein, Internet, Molecular Sequence Data, Protein Conformation, Proteins, Pseudomonas aeruginosa, Sequence Alignment, Sequence Analysis, Protein, Sequence Homology, Amino Acid, Software, Structure-Activity Relationship}, issn = {1362-4962}, doi = {10.1093/nar/gkm236}, author = {Marti-Renom, Marc A and Pieper, Ursula and Madhusudhan, M S and Rossi, Andrea and Eswar, Narayanan and Davis, Fred P and Al-Shahrour, F{\'a}tima and Dopazo, Joaquin and Sali, Andrej} }