Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Pair-end inexact mapping on hybrid GPU environments and out-of-core indexes

  • Salavert Torres, José|||0000-0001-6309-4401
  • Tomás Domínguez, Andrés Enrique
  • Blanquer Espert, Ignacio|||0000-0003-1692-8922
  • Medina Castelló, Ignacio
  • Sadakane, Kunihiko
[EN] Due to the NGS data deluge, sequence mapping has become an intensive task that, depending on the experiment, may demand high amounts of computing power or memory capacity. On the one hand, GPGPU architectures have become a cost-effective solution that outperforms common processors in specific tasks. On the other hand, out-of-core implementations allow to directly access data from secondary memory, which may be useful when mapping against big indexes in systems with low memory configurations. In this paper we discuss the implementation of backward search methods for inexact mapping in these two different study cases. A hybrid CPU-GPU implementation of a backward search algorithm capable of obtaining the pair-ends and the one error mappings of a read has been developed. This implementation can be used to increase the sensitivity and reduce the number of reads to be analysed with a dynamic programming approach. Also, a CPU out-of-core index using MMAP has been studied (provided by csalib). Such index can be used in memory limited scenarios, in which the time of loading many different big genomes into memory is greater than the time needed to map the reads., The authors would like to thank the Universitat Politècnica de Valencia (Spain) in the frame of the grant “High-performance tools for the alignment of genetic sequences using graphic accelerators (GPGPUs) / Herramientas de altas prestaciones para el alineamiento de secuencias genéticas mediante el uso de aceleradores gráficos (GPGPUs)”, research program PAID- 06-11, code 2025.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Fast inexact mapping using advanced tree exploration on backward search methods

  • Salavert Torres, José|||0000-0001-6309-4401
  • Tomás Domínguez, Andrés Enrique
  • Blanquer Espert, Ignacio|||0000-0003-1692-8922
  • Tárraga Giménez, Joaquín
  • Medina Castelló, Ignacio
  • Dopazo Blazquez, Joaquin
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., The authors would like to thank the Universitat Politecnica de Valencia (Spain) in the frame of the grant "High-performance tools for the alignment of genetic sequences using graphic accelerators (GPGPUs)/Herramientas de altas prestaciones para el alineamiento de secuencias geneticas mediante el uso de aceleradores graficos (GPGPUs)", research program PAID-06-11, code 2025.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Using GPUs for the exact alignment of short-read genetic sequences by means of the Burrows-Wheeler transform

  • Salavert Torres, José|||0000-0001-6309-4401
  • Blanquer Espert, Ignacio|||0000-0003-1692-8922
  • Tomás Domínguez, Andrés Enrique
  • Hernández García, Vicente
  • Medina Castelló, Ignacio
  • Tárraga Giménez, Joaquín
  • Dopazo Blazquez, Joaquin
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-theart 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., The authors would like to thank the Universitat Politecnica de Valencia in the frame of the grant "High-performance tools for the alignment of genetic sequences using graphic accelerators/Herramientas de altas prestaciones para el alineamiento de secuencias geneticas mediante el uso de aceleradores graficos (GPGPUs)," research program PAID-06-11, code 2025. They also want to thank Centro de Investigacion Principe Felipe for the support in the development of the work shown in this paper. Finally, special thanks to Mathieu Dubois and the personnel of Bull I+D HPC centre in Echirolles (France) for his excellent introductory course on CUDA.