PDF de programación - Parte de Algoritmos, de la asignatura de Programación Máster de Bioinformática Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Parte de Algoritmos, de la asignatura de Programación

Máster de Bioinformática

Aleatoriedad y algoritmos aleatorios

Domingo Giménez Cánovas

Departamento de Informática y Sistemas

Universidad de Murcia

http://dis.um.es/˜domingo/algbio.html

[email protected]

Aleatoriedad y algoritmos aleatorios

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Contenido

1 Aleatoriedad

2 Generación de números aleatorios (PERL 7.1 y 7.2)

3 Mutación en un ADN (PERL 7.3)

4 Generación de cadenas de ADN (PERL 7.4)

5 Estadísticas con cadenas de ADN (PERL 7.5)

6 Ordenación por Quicksort

7 Temas adicionales

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Está en la naturaleza (mutación).
Generación de valores aleatorios se puede usar para
simulación.
Son necesarias herramientas computacionales para generar
valores aleatorios.
Algoritmos aleatorios realizan operaciones o toman
decisiones distintas de forma aleatoria,

se pueden utilizar cuando explorar todas las posibilidades no
es posible
o para tomar una decisión cuando no se sabe cuál es la mejor

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Los lenguajes de programación tienen funciones para generar
números aleatorios.
En realidad son seudoaleatorios, pues generan una
secuencia de números, siempre la misma.
Empezando por una posición distinta (usando una semilla) se
puede simular que es aleatoria.
La semilla se puede establecer con un evento externo, por
ejemplo dependiendo de la hora.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.1 de PERL

→ Ejecutar el programa.
Escribe historias combinando de forma aleatoria partes distintas:

Almacena una serie de nombres, verbos y preposiciones
genera aleatoriamente un nombre, un verbo, un nombre y
una preposicion, y las concatena formando una historia.
Genera seis historias y pregunta si queremos continuar.
Utiliza el bucle do ... until,
y se acaba cuando lo escrito en la entrada estándar (STDIN)
es, desde el principio ( ˆ ), una serie de espacios en blanco
(\s*), seguido de (q), sin diferenciar mayúsculas y minúsculas
(i).

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.1 de PERL (continuación)

→ Localizar srand en el programa.
Se genera una semilla para la generación aleatoria con la función
srand:

srand(numero) generará los números aleatorios en las
sucesivas llamadas empezando en la posición de la
secuencia aleatoria indicada por numero.
Con srand(time|$$) se genera la semilla de forma
aleatoria:
time devuelve un número que representa el tiempo
y con $$ se concatena (operador .) con un número asociado
al programa que se está ejecutando.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.1 de PERL (fin)

→ Localizar rand en el programa.
Con sucesivas llamadas a la función rand se generan números
aleatorios.
Por ejemplo, $verbs[int(rand(scalar @verbs))] se evalúa de
dentro a fuera:

@verbs es un array
scalar @verbs devuelve que el array tiene 7 elementos
rand(scalar @verbs) devuelve un número real entre 0 y 7
con int(rand(scalar @verbs)) se toma como entero
y $verbs[int(rand(scalar @verbs))] devuelve el
elemento ($) en esa posición del array verbo.

y se puede escribir también $verbs[int rand scalar @verbs]
o $verbs[rand @verbs]

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.1 de PERL (modificación)

→ Modificar el ejemplo 7.1 para que no se generen historias
donde los dos nombres coincidan.

¿Otros cambios?

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.2 de PERL

Usa funciones para:

Seleccionar una posición aleatoria en una cadena de ADN,
seleccionar aleatoriamente un nucleótido
y sustituirlo en esa posición de la cadena.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.2: Posición aleatoria en ADN

sub randomposition {

my($string) = @_;
return int rand length $string;

}

Usa length para obtener la longitud del string que se le pasa,
y devuelve una posición aleatoria en él.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.2: Gererar un nucleótido

sub randomnucleotide {

my(@nucs) = @_;
return $nucs[rand @nucs];

}

Si se han guardado las cuatro posibilidades en

my @nucleotides = (’A’, ’C’, ’G’, ’T’);

devuelve uno de los cuatro caracteres.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.2: Cambiar una posición en la cadena

sub mutate {

my($dna) = @_;
my(@nucleotides) = (’A’, ’C’, ’G’, ’T’);

# Pick a random position in the DNA

my($position) = randomposition($dna);

# Pick a random nucleotide

my($newbase) = randomnucleotide(@nucleotides);

# Insert the random nucleotide into the random position in the DNA.
# The substr arguments mean the following:
# In the string $dna at position $position change 1 character to
# the string in $newbase

substr($dna,$position,1,$newbase);
return $dna;

}

→ Explicar el funcionamiento de la rutina a partir de los comentarios.
→ Ejecutar y entender el funcionamiento del programa completo.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.2 de PERL (modificación)

→ Modificar el ejemplo 7.2:

Para no cambiar un nucleótido por sí mismo.
Para cambiar un nucleótido por entre 1 y 4 nucleótidos. El
número se genera aleatoriamente y los caracteres también.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.3 de PERL

Con técnica de diseño top-down (en el caso anterior se ha usado
bottom-up):

@random_DNA = make_random_DNA_set( $minimum_length,
$maximum_length, $size_of_set );

donde:

repeat $size_of_set times:

$length = random number between minimum and maximum length
$dna = make_random_DNA ( $length );
add $dna to @set

return @set

etcétera, se llega al ejemplo 7.3

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.3 de PERL

→ Identificar la forma en que se ha diseñado el ejemplo 7.3.

→ Identificar las funciones reutilizadas.

→ Identificar nuevos operadores o funciones.

Domingo Giménez Cánovas

Aleatoriedad y algoritmos aleatorios

Aleatoriedad
Generación de números aleatorios (PERL 7.1 y 7.2)
Mutación en un ADN (PERL 7.3)
Generación de cadenas de ADN (PERL 7.4)
Estadísticas con cadenas de ADN (PERL 7.5)
Ordenación por Quicksort
Temas adicionales

Ejemplo 7.3 de PERL (modificación)

→ Modificar el ejemplo 7.3:

Para que las cadenas que se generen tengan un número par
de caracteres.
Para que en una cadena el número de caracteres de un tipo
no