Archive for the ‘TECNOLOGÍA Y APLICACIONES’ Category

Algoritmica y complejidad computacional. Nuevos resultados sobre permutaciones.

mayo 21, 2018

Compilamos en esta entrada dos nuevos “resultados” relacionados con el tema de permutaciones / grafos de Cayley, resultados que hemos visto muy por encima (prácticamente solo los títulos) y tenemos que mirar en detalle.  Aparentemente están relacionados, pero ya digo que tengo que mirarlos en detalle.

1.El primero  es un resultado que al parecer resuelve un problema que estaba abierto desde hacía tiempo. Los dos artículos son los siguientes.

–Circular support in random sorting networks, by Dauvergne and Virág,

–The Archimedean limit of random sorting networks by Duncan Dauvergne.

Una entrada de un blog en la cual hablan sobre este resultado.

2.El segundo es una solicitud de patente en EEUU. Y según hemos visto también es ¿ una patente coreana ?. Con el buscador cuántico de Google a veces es complicado volver a encontrar los resultados. Como el gato, a veces aparecen (estan vivis) y a veces no (estan muertos) ¿¿¿???.  Encontrada de nuevo. Es una aplicación también, entiendo que surcoreana:고전적 프로세서 상에서 양자-유사 계산을 에뮬레이트하기 위한 퀀톤 표현

El colega inventor es Arun Majumdar, y el titular es la empresa Kyndi Inc. Hemos encontrado esta solicitud de patente pues citan a una de las nuestras en ella.

Es curioso pues nuestro resultado utilizamos una terminología (entangled / entrelazado) que se utiliza también en mecánica / computación cuántica (conjuntamente con la superposición, el entrelazado sería uno de los fenómenos puramente cuánticos que harían posible una computación más rápida en los sistemas cuánticos con respecto a los clásicos; supuestamente), pero ya decimos en la propia patente que no tiene nada que ver con nada cuantico. En nuestro caso la utilizamos pues pensamos en su momento que es una palabra descriptivamente adecuada para la propiedad que intentamos describir con ella. No obstante esto nos da una idea:  estamos pensando constituir una sociedad que se llame “The Genomic Quantum Deep Learning Blockchain S.A.” 😉

Nota. Quede claro que no estamos ironizando sobre la empresa titular de la patente. Entre sus fundadores esta uno de los pioneros de la IA no basada en Machine Learning y en la empresa proponen un enfoque menos de caja negra. Obviamente, tampoco sobre el inventor. La ironia está relacionada con lo comentado en la entrada sobre criptomonedas. Fin de nota.

En fin, no pensamos que (el examinador) nos mencione por esto en concreto. En fin, espero que tras leerla en detalle no tengamos que decir en algún momento:

“¡¡¡ Cuan tontos fuimos por no haber visto esto antes !!!”.

Quanton representation for emulating quantum-like computation on classical processors

Abstract
The Quanton virtual machine approximates solutions to NP-Hard problems in factorial spaces in polynomial time. The data representation and methods emulate quantum computing on classical hardware but also implement quantum computing if run on quantum hardware. The Quanton uses permutations indexed by Lehmer codes and permutation-operators to represent quantum gates and operations. A generating function embeds the indexes into a geometric object for efficient compressed representation. A nonlinear directional probability distribution is embedded to the manifold and at the tangent space to each index point is also a linear probability distribution. Simple vector operations on the distributions correspond to quantum gate operations. The Quanton provides features of quantum computing: superpositioning, quantization and entanglement surrogates. Populations of Quantons are evolved as local evolving gate operations solving problems or as solution candidates in an Estimation of Distribution algorithm. The Quanton representation and methods are fully parallel on any hardware.

Extractos.

    DETAILED DESCRIPTION OF THE EMBODIMENTS

  • [0069]
    Performing an approximation to quantum computing by treating permutations as representative of model states provides the interpretation that all states are simultaneously computed by iteration. Treating distributions as approximating density functionals, estimating distributions, coupling these distributions to state spaces represented by permutations, computing based on these distributions, reasoning with these distributions over the symmetric group and structure learning using the present Quanton model are the central ideas as described by embodiments of the present disclosure.
  • [0070]
    The search space of solutions in permutation problems of n items is n factorial. The search space is usually denoted as Sn, in reference to the symmetric group of size n. In general, permutation problems are known as very hard problems when n goes above a relatively small number and their computational complexity demonstrated that many of the typical permutation problems is NP-hard. In view of their complexity, computing optimal solutions is intractable in general. For this reason, invented the Quanton in order to put in place a data structure designed to work, at worst approximately, and at best in certain special cases, exactly, at the factorial sizes of the search space.
  • [0071]
    Furthermore, noting that Quantum computing also has a very large space in terms of solution possibilities, the Quanton data structure and methods, using the unique, efficient and computable model described in the present disclosure built on the idea of permutation as computation (aka permutational quantum computing), the Quanton is devised herein to emulate Quantum computing as a virtual machine.
  • [0072]
    Now, referring to FIG. 1, which provides a Quanton Overview, there are two parts to the overall procedure: first, there is the local procedure for creating the Quanton for use in emulating localized (to the Quanton) computational operations and then there is the global procedure for evolving the Quanton or a population of Quantons to learn about incoming data problems. This is done in order to produce optimal solutions based on the procedure of Estimation of Distribution (EDA) algorithms, also known as Probabilistic Model Building Genetic Algorithm (PMBGA).
  • [0073]
    The Quanton uses embeds permutations in special way that allows the permutations to each have a unique index (by using a lattice) into a continuous probability space. The produces a unique encoding for operations that enable it to mimic quantum gates. Hence quantum gates are embedded in a continuous probabilistic vector space in which fast vector computations perform the equivalent of complex quantum gate operations, transforming inputs to outputs, or, equivalently, computing quantum transitions from state to state. Given that all permutations are simultaneously available as indexed on the Quanton, every continuous vector space operation, therefore, updates all permutations simultaneously since it is the probability density distribution that is performing the update. In this sense the Quanton represents a superposition of all potential solutions. The Quanton represents quantized discrete structure because of its lattice and entanglements are represented by correlations between variables that emerge as a result of an evolutionary process that surfaces the entangled states as solution sets to the input query state (i.e. the data to be learned or solved).

….

  •  A permutation distance function is used to measure the Quantum Gate solution. If the distance is small, then a solution is near. If the distance is far, then solution is still to be found. A critical piece of the Quanton is, therefore, the choice of a permutational distance function. There are several choices for the distance functions, such as the Hamming Distance between the output bit-strings of gate operations or Levenstein Distance as an edit distance between bit strings of the gate operations. However, the disclosure uses a permutational distance that is more closely aligned with the probabilistic nature of quantum systems: the distance measurement on permutations is based on the generalized Mallows model following the teachings of J Ceberio, E Irurozki, A Mendiburu, J A Lozano, “A review of distances for the Mallows and Generalized Mallows estimation of distribution algorithms”, Computational Optimization and Applications 62 (2), 545-564 and is incorporated herein in its entirety.
  • [0085]
    The distance measure is an analog to the Levenstein Edit distance measure between strings except that in this case, The Mallows model is use which is a distance-based exponential model that uses the Kendall tau distance in analogy with the Levenstein measure: given two permutations σ1 and σ2, the measure counts the total number of pairwise disagreements between σ1 and σ2 which is equivalent to the minimum number of adjacent swaps to convert σ1 into σ2. As noted in section of the present disclosure corresponding to FIG. 39, this is actually equivalent to a Quantum Gate operator in the Quantum Permutational computation regime presented in this disclosure. Hence, the evolution, using this distance measure, seeks optimal quantum circuits performing the problem solving.

Por lo que hemos resaltado en negrita, pensamos que los dos resultados mencionados podrían estar relacionados, pero ya decimos que tenemos  que verlos los dos con mas detalle…

Actualizaremos la entrada en su momento.

Anuncios

Teoria general de las criptomonedas: economia y negocios / inversion.

mayo 5, 2018

Esta es una nueva version del texto que aparecia en la postdata de la entrada anterior. Ya dijimos que seguramente hariamos una entrada especifica y eliminariamos el texto de la parte anterior.

Seguimos trabajando en el tema sobre todo en determinados puntos mas cuantitativos. La version sera definitiva cuando eliminemos estas dos ultimas frases.

Escribimos desde el smartphone. No nos resulta comodo poner acentos y a veces el corrector juega malas pasadas. Pedimos disculpas al lector por ello.

(more…)

IP. El caso CRISPR.

mayo 2, 2018

En esta entrada combinamos muy brevemente dos materias que nos interesan: la propiedad intelectual y la genetica / genomica (sobre la que hemos hablado en las recientes entradas).

Y lo hacemos muy brevemente. Con un enlace. 

Al parecer hay un problema de patentes de por medio. Cuando nos documentemos quizas ampliemos la entrada.

 

 

Complejidad computacional. La complejidad de algunos problemas bioinformáticos.

abril 24, 2018

1.A raíz de la última entrada estoy leyendo sobre técnicas bioinformáticas.

Es interesante pues en un método bioinformático se combinan pasos puramente bioquímicos / biomoleculares, cuya lógica solo los expertos o iniciados pueden llegar a comprender con pasos puramente informáticos (que incluso alguien como el que escribe estas líneas puede llegar a comprender).

Como ejemplos de pasos u operaciones biomoleculares podemos poner los siguientes (note el lector la similitud entre algunas de las operaciones biomoleculares y los componentes de un lenguaje de programación):

–la electroforesis, que separa una cadena molecular,sea de nucleotidos, de aminoacidos o de cualquier otro tipo de componentes, en partes más pequeñas,

–el famoso PCR o la clonación molecular, que permiten replicar-multiplicar una determinada cadena molecular de manera eficiente (en este caso se considera eficiente lo exponencial),

–la sonda de hibridación, que hace las funciones de un molde que permite determinar si una determinada cadena molecular existe en una “solución” bioquímica,

–las técnicas de fluorescencia, que permiten identificar componentes de una cadena molecular o mas en general etiquetar componentes bioquimicos,

Combinando las operaciones anteriores se pueden obtener ya verdaderos “algoritmos” biomoleculares, como:

–el método de Sanger, que supone la primera generación de métodos de secuenciación: Gracias a la incorporación de las técnicas fluorescentes, el diseño de fluoróforos, el avance en enzimología y la introducción de la electroforesis capilar, el método de Sanger aumentó su eficiencia, pasando a ser conocido como el método de Sanger automatizado, y marcando el inicio de las tecnologías de secuenciación de primera generación.  

los métodos de secuenciación segunda generación (NGS), también llamados High-throughput DNA sequencing o Massively Parallel Sequencing. Desde 2010 ya se comercializan sistemas de tercera generación que obtienen reconstrucciones de genomas de mejor calidad (here we consider third generation technologies to be those capable of sequencing single molecules, negating the requirement for DNA amplification shared by all previous technologies; se trata de obtener la mayor cantidad de información posible con los pasos puramente biomoleculares directos, evitando así los pasos biomoleculares de fraccionamiento y amplificación y la cocina puramente informática asociados a ellos; se obtienen lecturas de segmentos más largos que exigen menos cocina). No tengo claro el estatus actual de esta nueva tecnología. Parece que en el momento de escribir estas líneas, al menos han encontrado su nicho. Más sobre esto en el punto  2 de esta entrada.

–el Southern Blot, método de detección de secuencias, que combina varias de las técnicas anteriores para detectar secuencias moleculares o su evolución,

–el Microarray o chip que, cómo el anterior, permite la detección de secuencias moleculares de forma masiva en paralelo, etc…).

Como se ve, las máquinas bioinformáticas, son un tipo muy diferente de máquinas a las que estamos acostumbrados a ver, y combinan ambos tipos de pasos para resolver problemas bioinformáticos. El input suele ser bioquímico / biomolecular y a lo largo del método se combinan técnicas bioquímicas e informáticas para obtener un output que suele ser puramente informático.

Hay varios tipos de problemas bioinformáticos (posiblemente un nombre mas adecuado para los temas sobre los que hablamos en esta entrada sea el de genomica computacional) que destacan sobre los demás: secuenciación de ADN (dada una molecula de adn, que es un input bioquímico, determinar su secuencia de nucleotidos, secuencia que se puede expresar como una palabra en un alfabeto de cuatro letras y por lo tanto es un output informático), alineamiento de secuencias de ADN (el alineamiento es la comparación de dos o más secuencias bioquímicas; ahora mismo no sabría expresar este problema en forma de input / output bioquímicos / informáticos), ensamblado de secuencias de ADN  (dadas una serie de secuencias, que serían el input, ensamblar un genoma completo, que sería el output),  plegamiento de proteínas (dado como input la estructura primaria de una proteina determinar su estructura terciaria, que sería el output; idem anterior). No son los únicos. Según recuerdo ya hemos comentado en algunas entradas sobre algunos de estos problemas.

He encontrado un artículo interesante sobre la complejidad computacional de los pasos puramente informáticos (a los que se puede llamar algoritmos) de los métodos bioinformáticos.

Complexity issues in computational biology
Jacek Blazewicz Marta Kasprzak∗
Institute of Computing Science, Poznan University of Technology,
and Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland

Abstract
The progress of research in the area of computational biology, visible in last decades, brought, among others, a new insight into the complexity issues. The latter, previously studied mainly on the ground of computer science or operational research, gained by a confrontation with problems from the new area. In the paper, several complexity issues inspired by computational biology are presented.

La fecha del artículo debe de ser 2011 o 2012. Me ha interesado pues comentan que, primero, para resolver estos problemas primero se generan grafos, y segundo el problema que se debe de resolver en muchos casos es el problema de recorridos hamiltonianos.

 The paper is organized as follows. Section 2 describes several classes of graphs with the background in computational biology and their impact on computational complexity of combinatorial problems. In  Section 3 it is shown how presence or absence of experimental errors affects computational complexity of biological problems, resulting even in a distinct way of proving their NP-hardness. Similarities and differences between DNA computers and nondeterministic Turing machines are discussed in Section 4. We conclude the paper in Section 5.

Hago la entrada para leerlo con más detalle en otra ocasión. Si tras la lectura en diagonal del artículo me he enterado bien, sólo se trata de la complejidad computacional de los pasos puramente informáticos. Sin embargo entiendo que también se debe de considerar la complejidad de los pasos puramente bioquímicos. Por ejemplo el PCR hace uso de la reproducción exponencial. Dejamos este apunte sobre un tema que requiere mayor estudio.

2.Es interesante que la emergencia de la biología moderna (la biología molecular, en gran parte basada en la revolución del ADN) es casi contemporánea de la emergencia del computador electrónico.

Si un computador electrónico trata de controlar la corriente eléctrica para representar inputs y manipularla para resolver cálculos, una máquina bioinformática trata de controlar procedimientos biomoleculares / bioquímicos para resolver problemas, de momento, biológicos. Y lo hace apoyándose en la informática. En general se trata de convertir información que está en forma biomolecular o bioquímica en información puramente informática. De extraer de los objetos biologicos la información que contienen. La informática es la herramienta, el medio; la biología es el producto, el fin. De esta concepcion de la bioinformatica es de la que hablamos en esta entrada.

Nota. En realidad, al final, de lo que se trata es no solo de extraer información (de esto, gracias a los avances en los métodos que se han ido reseñando, ya hay abundantes bases de datos), sino conocimiento, entre otras para aplicaciones médicas o agroalimentarias. Y en esto la genómica sigue siendo, al parecer, una promesa. Todavía en 2018. Por supuesto con algunos éxitos, como el que hemos reseñado en la entrada anterior sobre arqueogenética.

Obviamente, el sector biotech (nuevo nombre para viejo sector) es mucho mas amplio que el sector de la genómica. Se basa en muchas otras tecnologías, se utilizan muchos otros tipos de máquinas,  y está muy sano. Fin de nota.

Por otra parte, como el lector sabe, la idea de controlar procesos bioquímicos para resolver problemas que no tienen nada que ver con la biología ya existe y se llama biocomputación, cosa muy diferente a la bioinformática. En el caso de la biocomputación, representamos un problema cualquiera en forma bioquímica, y se utilizan métodos bioquímicos (y entiendo que también informáticos) para resolverlos. El output será una forma bioquímica que podemos traducir fácilmente a una forma informática. La biología es la herramienta, el medio; el tratamiento de la información (el calculo)  es el producto, el fin. Este campo de la biocomputación sigue, al parecer, avanzando (resultado de 2013, en el que hablan de las Bil Gates) y avanzando (resultado de 2016, según un artículo periodístico, y el correspondiente artículo técnico: Parallel computing with molecular motor-propelled agents in nanofabricated networksBy Dan V. Nicolau, Jr et al. 2016. PNAS), pero no sabemos si ya hay una industria vinculada a estos avances. Quizás se necesite un idem para ello. Al margen de estos proyectos biocomputacionales, es posible que los actuales bioinformáticos estén ahora mismo, sin saberlo, con fines puramente biológicos, diseñando las herramientas que se utilizarán en los biocomputadores (sin finalmente esta tecnología se acaba adoptando).

Nota. La terminología no está del todo clara, como queda patente en este artículo. Fin de nota.

En fin, como hemos visto en el primer punto, las máquinas bioinformáticas son producto de la convergencia de estos dos campos, la biología molecular y la ingeniería electrónica. A continuación compilamos algunos artículos que nos cuentan como ambos llegaron a converger y sobre la organización de este sector económico, según vayamos encontrando. Es curioso ver que aunque los dos campos convergen, siguen siendo compartimentos estancos: por ejemplo, diría que los algoritmos de bioinformática y sus autores son poco conocidos entre los informáticos.

–The origins of bioinformatics.

Abstract

Bioinformatics is often described as being in its infancy, but computers emerged as important tools in molecular biology during the early 1960s. A decade before DNA sequencing became feasible, computational biologists focused on the rapidly accumulating data from protein biochemistry. Without the benefits of super computers or computer networks, these scientists laid important conceptual and technical foundations for bioinformatics today.

–uno de los subcampos de la bioinformática son las bases de datos de objetos biológicos como genes (secuencias de nucleótidos), proteínas (secuencias de aminoácidos) etc…y su fácil manipulación (de las bases de datos). La pionera en este campo fue Margaret Dayhoff , cuyo primer contacto con un sistema informático fue en 1957. En  1962 co-publicó un artículo entitled “COMPROTEIN: A computer program to aid primary protein structure determination” that described a “completed computer program for the IBM 7090” that aimed to convert peptide digests to protein chain data. They actually began this work in 1958, but were not able to start programming until late 1960.

–1970. Algoritmo de Needleman-Wunsch para alineamiento de secuencias de nucleotidos. Basado en programacion dinamica.

–1973, Edwin Southern crea el método Southern blot. En este artículo analizan el tema desde el punto de vista de la propiedad intelectual y del emprendimiento: Southern era academico, cedio al dominio publico su invención (no tenía más remedio), pero en 1995, cuando cambió la actitud con respecto al emprendimiento por parte de académicos creó una biotech, Oxford Gene Technology.

–1976-1977. Método (biomolecular) de secuenciación Maxam-Gilbert.  Allan Maxam and Walter Gilbert’s 1977 paper “A new method for sequencing DNA” Es el primer método de la primera generación.  Gilbert recibió el Premio Nobel por este método. Maxam era un estudiante de doctorado de Gilbert.

–1977. Frederick Sanger desarrolla el método (biomolecular) de secuenciación que lleva su nombre. Es de los pocos investigadores que ha recibido dos premios Nobel. Uno por secuenciar proteinas (insulina). Otro por secuenciar ADN (phi x 174) y por el método de secuenciación que lleva su nombre.

Como se ve la obtención de las primeras secuencias se hizo de manera artesanal. Pero en los 70 las necesidad de métodos generales y rápidos de secuenciación: The first method for determining DNA sequences involved a location-specific primer extension strategy established by Ray Wu at Cornell University in 1970.[14] DNA polymerase catalysis and specific nucleotide labeling, both of which figure prominently in current sequencing schemes, were used to sequence the cohesive ends of lambda phage DNA.[15][16][17] Between 1970 and 1973, Wu, R Padmanabhan and colleagues demonstrated that this method can be employed to determine any DNA sequence using synthetic location-specific primers.[18][19][20] Frederick Sanger then adopted this primer-extension strategy to develop more rapid DNA sequencing methods at the MRC CentreCambridge, UK and published a method for “DNA sequencing with chain-terminating inhibitors” in 1977.[21] Walter Gilbert and Allan Maxam at Harvard also developed sequencing methods, including one for “DNA sequencing by chemical degradation”. 

–1979. Artículo de Rodger Staden. Presenta un primer programa de secuenciación de ADN. Al parecer se sigue utilizando. 

–1981. Algoritmo de Smith-Waterman. Para alineamiento de secuencias. Basado en programacion dinamica.

–1990. BLAST. Heuristica para búsqueda de secuencias en bases de datos. Varios autores. Se parte de una secuencia lineal y completa dada y se buscan secuencias lineales y completas similares disponibles en las bases de datos disponibles. Es una variante del problema de alineamiento.

–1994. Transformada (algoritmo) de alineación Burrows-Wheeler. Método de compresión que combinado con otros métodos se utiliza para alineamiento o mapeado de lecturas (que suponen un muestreo del genoma completo secuenciado por NGS). Esta es otra variante del problema de alineamiento. En este caso el input es por un lado una secuencia de referencia en forma lineal y completa (por ejemplo un genoma completo humano obtenido anteriormente y disponible en alguna base de datos) y por otro lado un conjunto de “lecturas” (palabra técnica) obtenido al aplicar un método NGS. Esta alineación o mapeado es otra operación básica, consecutiva a la secuenciación NGS, que se utiliza como paso previo para otros objetivos de mayor contenido biológico (genotipado, asignación de SNPs, obtención del exoma etc…). El conjunto de lecturas suponen una muestra del genoma secuenciado y mapeando esta muestra al genoma de referencia podemos obtener estos otros objetivos.  En este caso los creadores de la transformada eran informáticos y su objetivo no era bioinformático. Existe una implementación optimizada de este método llamada BWA, que es muy utilizada. Pero hay otros muchos métodos

Secuenciación de genomas. Historia, estado del arte y futuro. La secuenciación de genomas (o proteinas) es el campo dónde más se pone de manifiesto la interacción entre lo biomolecular y lo informático. Proporciona la materia prima (secuencias de nucleotidos o de aminoacidos) que luego se va a utilizar en todos los otros métodos. Por ello se ha invertido mucho esfuerzo en obtener métodos rápidos y económicos, con éxito. Como hemos visto a mediados de los 90, y más todavía en los 2000 se pasa de necesitar métodos rápidos (que es lo que proporcionan las técnicas de primera generación)  a necesitar métodos industriales, de un rendimiento de una escala mucho mayor, y se obtienen los métodos ya comentados como el Microarray o los NGS. Hoy abundan los métodos de secuenciación. Y ya se puede escribir una historia sobre el tema, ordenada por generaciones de secuenciadores.

Esto es lo que han realizado en este interesante artículo. : The sequence of sequencers. History of sequencing DNA (2015).    Extracto: We review the drastic changes to DNA sequencing technology over the last 50 years. First-generation methods enabled sequencing of clonal DNA populations. The second-generation massively increased throughput by parallelizing many reactions. Third-generation methods allow direct sequencing of single DNA molecules.

Lo mismo hacen en este artículo de Nature de 2017. DNA sequencing at 40: past, present and future. This review commemorates the 40th anniversary of DNA sequencing, a period in which we have already witnessed multiple technological revolutions and a growth in scale from a few kilobases to the first human genome, and now to millions of human and a myriad of other genomes. DNA sequencing has been extensively and creatively repurposed, including as a ‘counter’ for a vast range of molecular phenomena. We predict that in the long view of history, the impact of DNA sequencing will be on a par with that of the microscope.

En este enlace una presentación bastante técnica y de 2013 sobre las tecnologías de secuenciación.

Y en este muy interesante artículo de 2017, escrito por un experto, aunque en un estilo periodístico, nos comentan sobre la organización industrial del sector y sobre los proyectos publicos o privados de genómica alcance nacional presentando una serie de datos muy interesantes:  The next generation sequencing (NGS) market, including but not limited to WGS, was valuedat €4.6Bn in 2015 and is expected to reach €19Bn by 2020. Many private companies, such as Illumina, Roche, Life Technologies and Pacific Biosciences, are rushing into NGS to answer the rising sequencing needs…../…..Back in 2003, the International Human Genome Sequencing Consortium kicked-off the genome analysis race by sequencing a complete human genome after years of worldwide collaboration and billions of investment. A few years later, the price of WGS reached $1,000. According to Illumina, it is “expected one day” that whole genome sequencing will cost less than $100. On one hand, pocket NGS is not yet practical or economical. On the other hand, most available equipment is still quite expensive. For example, Illumina’s NovaSeq 5000 costs around €800,000 and a NovaSeq 6000 reaches almost €1M…./….In 2016, France announced the “France Medecine Genomique 2025” program, aiming to open 12 sequencing centers and ensure 235,000 WGS a year. The French government is planning to inject €670M in this program, whose main aim is to use WGS as a diagnostics tool. Last but not least, China has been an unbeatable leader in genome sequencing for years now. In 2010, the BGI genomics institute in Shenzhen was probably hosting a higher sequencing capacity than that of the entire United States. China’s sequencing program is not just aiming for thousands but rather one million human genomes and will include subgroups of 50,000 people, each with specific conditions such as cancer or metabolic disease. There will also be cohorts from different regions of China “to look at the different genetic backgrounds of subpopulations.”…../…..It is difficult to anticipate the impact of WGS in modern medicine, but ethical issues regarding privacy of health data have already emerged. It is obvious that no one would like to see GAFA (Google, Apple, Facebook, Amazon) selling genome data as they are probably already doingwith personal data from their users.

Un muy interesante artículo sobre las fuerzas que están presionando los costes de secuenciación de genomas a la baja. Al principio nos ilustran a viste de pájaro sobre el desarrollo del sector: In the 1950s, the contemporaneous development of biopolymer sequencing and the digital computer started a digital revolution in the biosciences. Then in the late 1970s, the advent of the personal computer (PC) and Sanger sequencing led to an appreciable amount of sequence data being generated, stored in databases, and conceptualized within a computational framework [1234]. Communal sequence databases were developed in the 1980s [56], but most investigators worked with data of a scale that allowed transfer to and processing on a local client. In the 1990s, the rise of the Internet facilitated increased data sharing, and analysis techniques began to shift to programs hosted on websites [7]. In the mid-2000s, the most recent big change occurred with the advent of cloud computing and next generation sequencing (NGS), which led to a dramatic increase in the scale of datasets (Fig 1) [48]. This necessitated changes in the storage infrastructure; databases such as the European Nucleotide Archive [9] and the Sequence Read Archive (SRA) [10] were created to store and organize high-throughput sequencing data. The SRA has grown significantly since its creation in 2007, and it now contains almost four petabases (4 × 1015 bases), approximately half of which are open access [11]. These datasets present a challenge because they are too large for the old sharing and analysis paradigms, but recent innovations in computational technologies and approaches, especially the rise of cloud computing, provide promising avenues for handling the vast amounts of sequence data being generated.

–A diferencia de los métodos de secuenciación que combinan pasos biomoleculares con pasos puramente informáticos, los métodos de solución del problema de alineamiento NGS (por llamarlo de alguna manera, el lector comprenderá) son puramente informáticos. En la introducción de este artículo dónde hablan de un nuevo algoritmo llamado Kart, nos hacen una buena presentación de la situación a vista de pájaro:

Next-generation sequencing (NGS) allows biologists to investigate genome-wide variation at nucleotide resolution. It has contributed to numerous ground-breaking discoveries and become a very popular technique for sequencing DNA and characterizing genetic variations in populations. Since new sequencing technologies can produce reads on the order of million/billion base-pairs in a single day, many NGS applications require very fast alignment algorithms. The traditional sequence alignment approaches, like BLAST (Altschul et al., 1990) or BLAT (Kent, 2002), are unable to deal with the huge amount of short reads efficiently. Consequently, many aligners for NGS short reads have been developed in recent years. They can be classified into two categories according to their indexing methods: hash tables and suffix array/BWT. A hash table based aligner uses all the subsequences of k-mers to obtain the occurrence locations. In contrast, a suffix array/BWT based aligner finds the maximal exact matches (MEM) between the read sequence and the reference genome. Each category of read aligners has its own merits and deficiencies. However, suffix array/BWT based aligners are more popular due to the efficiency of memory consumption.

Aligners based on hash tables include CloudBurst (Schatz, 2009), Eland (proprietary), MAQ (Li et al., 2008a), RMAP (Smith et al., 2008), SeqMap (Jiang and Wong, 2008), SHRiMP (Rumble et al., 2009), ZOOM (Lin et al., 2008), BFAST (Homer et al., 2009), NovoAlign (proprietary), SSAHA (Ning et al., 2001), and SOAPv1 (Li et al., 2008b). Most hash table based aligners essentially follow the same seed-and-extend strategy (Li and Homer, 2010). A representative algorithm of this strategy is BLAST. BLAST keeps the occurrence locations of each k-mer of the database sequences in a hash table and then uses the given query’s k-mers to scan and find exact matches by looking up the hash table. An exact match is used as a seed to extend the alignment using Smith-Waterman algorithm between the query and the reference sequence.

Aligners based on suffix array or using Burrorws-Wheeler transform (BWT) (Wheeler, 1994) include Bowtie (Langmead and Salzberg, 2012Langmead et al., 2009), BWA (Li and Durbin, 2009), BWA-SW (Li and Durbin, 2010), BWA-MEM (Heng Li), SOAPv2 (Li et al., 2009), CUSHAW (Liu et al., 2012), Subread (Liao et al., 2013), HISAT/HISAT2 (Kim et al., 2015), HPG-aligner (Tarraga et al., 2014)and segemehl (Hoffmann et al., 2009). Most aligners in this category rely on a suffix array to identify the maximal exact matches (called MEMs) and then build alignments based on the exact matches, which is also similar to the seed-and-extend methodology. One exception is the Subread aligner, which adopts a seed-and-vote step to determine the mapped genomic location with multiple seeds from a read sequence. The major advantage of using suffix arrays is that repetitive subsequences need to be aligned only once because they are collapsed onto a single path (Li and Homer, 2010).

Though current short read aligners provide solutions for mapping the massive amount of read sequences produced by NGS technologies, some are not fast enough and some are not accurate enough. Moreover, the third generation sequencing technologies raise further challenges for data analysis, namely, extremely long read sequences and much higher error rate. For example, the PacBio RS II system can generate reads in the length of 5500–8500 bp on average, but the single-read accuracy is only about 87%. Most short read aligners have difficulty in processing those read sequences.

–Como estamos viendo, la algorítmica vinculada a problemas de genómica NGS es bastante nueva, pero la temática ya da para escribir un libro (2017): Algorithms for Next-Generation Sequencing Data: Techniques, Approaches, and applications. Mourad Elloumi.  Tiene una parte de indexado, compresión y almacenaje; una parte de métodos de corrección de errores; una parte para los algoritmos de alineación NGS; y una parte para los algoritmos de ensamblado.

–La bioinformática (y más en concreto la genómica computacional), no se reducen a los métodos de secuenciación. Una buena presentación de la situación actual de la bioinformática.

un informe sobre la situación de la genética clínica y genómica en España.

 

IP. La propiedad intelectual en el nacimiento de las computadoras contemporaneas.

marzo 24, 2018

1.Seguimos con entradas vinculadas a las lecturas recientes.

Concretamente estamos leyendo entre otros un libro titulado Historia y critica de la informatica, de Philippe Breton.

Es de 1987 y por lo tanto anterior a Internet, lo cual lo hace mas interesante.

2. Queda claro que ya en la segunda mitad de la decada de los 30 del siglo pasado se empiezas a impulsar variados proyectos de computadores basados en diversas las tecnologias que hemos comentado en la entrada anterior: Zuse y su serie Z, Atanasoff y Berry y su ABC, Aiken y su Harvard Mark 1, Stibitz y su Model 1, y el ENIAC de Eckert y Mauchly. Seguramente la lista no es exhaustiva.

Nota. Cual era la situacion del tratamiento automatico de la informacion (incluimos el calculo aritmetico o numerico) antes de estos proyectos que acabamos de citar ?.

(more…)

El computador hidraulico.

marzo 23, 2018

Seguimos con entradas cortas inspiradas por las recientes lecturas. En esta ocasion mostramos una curiosidad.

Nota. En mayo de 2017, ultimo periodo en el que tuvimos tiempo para dedicar a estos temas escribimos una entrada de contenido similar pero mucho mas detallada y con muchos mas enlaces.

En esta entrada se ve claramente como la aplicacion / motivacion principal de los implicados en el diseno de maquinas computacionales era la elaboracion de tablas: astrnomicas, balisticas, de navegacion, actuariale, censos etc…

Fin de nota.

 

1.La computacion actual esta basada en el fenomeno de la electricidad, que no es mas que un flujo de electrones.

(more…)

Lo analógico, lo digital, lo cuántico: Vannevar Bush vs. Claude Shannon vs ¿?.

marzo 15, 2018

Esta entrada va sobre tres temas entrelazados que serán aparentes (y hacemos explícitos mediante tres notas) a medida que el lector vaya avanzando.

(more…)

Otros parámetros relevantes en los casos (3,3) generados.

septiembre 24, 2017

Actualización 15 octubre 2017.

En una entrada anterior de mayo de 2016 en la que comentamos sobre una generalización al resultado de Milnor,  hacíamos el siguiente comentario.

3. ¿ No podría generalizarse esta técnica a otros casos (2-n) generalizados ?. Entiendo que como mucho a los (2-4) generados.  A partir de aquí, el tema está tan abierto que determinar los paths posibles cuando se recorres la zona en la que no se encuentra el IAS identidad, puede empezar a ser complejo. Estudiaremos los casos (2-4) generados.

En esta entrada vemos que no es el unico caso.

Fin actualización.

El teorema de Milnor sobre casos (2,3) generados, sobre el que hicimos varias entradas bastante detalladas el ano pasado (en la ultima esbozabamos una generalizacion aplicable a estos mismos casos 2,3 generados), se puede “generalizar” en otros dos sentidos: analizando casos (2,n) generados (cosa que hemos realizado tambien en anteriores entradas sobre casos 2,4 generados, 2,5 generados y 2,6 generados) o analizando casos (3,3) generados, es decir aquellos en los que los dos generadores son de orden 3.

El análisis de estos casos (3,3) generados nos hace ver que, al igual queqhay sucedia para los casos 2,3 generados, hay otros parámetros clave para determinar si existen recorridos hamiltonianos en estos casos. Es decir, el orden de los dos generadores, el orden del IAS y del DAS, el orden de la circunferencia no son suficientes.

Si los generadores son x e y, los otros dos parámetros relevantes son (xy)^n=1 y (xxyy)^n=1.

Recordamos que en los casos 2,3 generados el parametro clave era el n de la relacion (xy^2)^n=1.

El lector puede comprobarlo analizando un caso de S4 con dos generadores de orden 3, IAS6 y circunferencia 2 (y por lo tanto 1/2 entangled). El análisis de este caso es muy ilustrativo y ? seguramente ?se puede generalizar a todos los casos (3,3) generados. El tema no esta 100% claro.  Por experiencia sabemos que no conviene extrapolar demasiado lo que ocurre en casos pequenos. Lo veremos en otra entrada cuando tengamos tiempo de desarrollar el tema.

Por otra parte he visto que al igual que los casos (2,3) generados, los casos (3,3) generados han sido bastante estudiados por la teoría de grupos de principios del XX: es parte del estudio de los

grupos abstractos de tipo (l,p| q,r),

siguiendo la expresión de Coxeter. Este autor y anteriormente otros como W.A. Edington, Miller, Sinkov y otros los han estudiado.

Un artículo de principios del XXI sobre el tema:

The abstract groups (3, 3 | 3, p). 

The two-generated abstract groups (l, m | n, k) defined by presentations
(l, m | n, k) = <x, y | x^l = y^m = (xy)^n = (x^−1y)^k>i (2)
were first studied by Edington [3], for some small values of  l, m, n and k.

The notation we use was devised by Coxeter [1] and Moser [2], and has a
deeper meaning that we will not discuss here.

From now on, we will always refer to presentation (2) when speaking about (l, m | n, k).

The starting point for our discussion is Theorem 2, due to Edington [3,
Theorem IV and pp. 208210]. (Notice that there is a typo concerning the
order of (3, 3 | 3, n), and a misprint claiming that (3, 3 | 3, 3) is isomorphic
to A4.). For the convenience of the reader, we give a short, contemporary
proof.

Theorem 2 (Edington). The group G = (3, 3 | 3, n) exists for every n > 1,
is of order 3n^2, and is non-abelian when n > 1. It contains a normal
subgroup H = <x^2y, xy^2>i ∼= Cn × Cn. In particular, G ∼= C3 when n = 1,
G ∼= A4 when n = 2, and G is the unique non-abelian group of order 27 and
exponent 3 when n = 3.

(more…)

Grandes almacenes: una perspectiva global.

agosto 30, 2017

De nuevo una imagen vale por mil palabras. La fuente de la imagen es el gran blog modaes.es

Unos muy breves comentarios.

(more…)

Ip. La prueba documental.

agosto 6, 2017

Por el titulo nos referimos a las pruebas documentales de la concesion de la segunda patente.

La recepcion por correo.

Y en las siguientes imagenes la primera pagina de la segunda, las portadas de las dos y las primeras paginas de las dos.