Algorithmie en Java

egaetan
53.8K views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

ADN [Difficile]

Inspiré de BattleDev Novembre2017

Enoncé

Vous avez pour mission d’évaluer le potentiel génétique des candidats d’un nouveau centre spatial 🌠. Pour cela, vous avez développé une méthode de séquençage de leur ADN. Le candidat est une espèce à 1 chromosome double brin. C’est-à-dire que son ADN peut être vu comme deux chaînes de caractères a et b composées exclusivement des lettres A, C, G et T. Par ailleurs ces deux chaînes sont complémentaires, elles sont donc de même longueur et vérifient :

  • a[i] = A ⇔ b[i] = T
  • a[i] = T ⇔ b[i] = A
  • a[i] = C ⇔ b[i] = G
  • a[i] = G ⇔ b[i] = C

Lors du séquençage, les deux chaînes se cassent en plusieurs petits fragments qui sont mélangés entre eux. Votre méthode n’est pas si mauvaise que ça, vous savez que l’ordre des caractères dans un fragment n’a pas été inversé. Vous êtes cependant obligé écrire un programme pour recoller les morceaux dans un ordre plausible. Pour vous assurer que vous n’avez oublié aucun fragment, votre programme renverra les deux chaînes a et b en séparant les différents fragments par des espaces.

Indication : l’ADN d’un candidat n’est pas très complexe, il n’y aura jamais plus de 8 fragments, vous pourrez donc procéder par énumération exhaustive (force brute).

Exemple

Si vous avez les fragments suivants :

  • AT
  • G
  • CC
  • TAG

Une solution possible est alors :

Brin1TAG G
Brin2AT CC

Ce qui donne la sortie suivante (voir plus bas pour le format de sortie) :

TAG␣G#AT␣CC

On pourrait bien sûr permuter les brins 1 et 2 et la solution serait aussi correcte.

Format des données

Entrée

Ligne 1: un entier N compris entre 2 et 8, indiquant le nombre de fragments d’ADN.

Lignes 2 à N+1: une chaine comprenant entre 1 et 16 caractères, composée exclusivement des lettres A, T, C, et G représentant un fragment.

Sortie

Une chaîne de caractères représentant les 2 brins. Les 2 brins sont séparés par le caractère # et dans un brin donné les fragments utilisés sont séparés par des espaces.

Explications

Le sujet consiste à brute-forcer toutes les combinaisons possibles pour trouver une solution.

Brut-force

Méthodologie :

  • Générer toutes les combinaisons
  • Tester les combinaisons
Générer les combinaisons

Le plus simple est la méthode récursive.

On considère que l'on va générer toutes les combinaisons de nombres de 1 à N, correspondants

  • On choisit le premier élément
  • puis le second en vérifiant que le second est différent du premier
  • puis le troisième en vérifiant le troisième est différent du premier et du second
  • ...
  • puis le nième en vérifiant qu'il est différent du premier, second, ... et du (n-1)ème
public <T> List<List<T>> allCombinaisons(List<T> source) {
	return allCombinaisons(source.size(), new ArrayList<>(), source.size())
		.stream()
		.map(l -> l.stream()
					.map(i -> source.get(i))
					.collect(Collectors.toList()))
		.collect(Collectors.toList());
}

public List<List<Integer>> allCombinaisons(int nb, List<Integer> passed, int n) {
	List<List<Integer>> res = new ArrayList<>();
	if (n == 0) {
		return Collections.singletonList(passed);
	}
	for (int i = 0; i < nb; i++) {
		if (passed.contains(i)) {
			continue;
		}
		List<Integer> passedNext = new ArrayList<>(passed);
		passedNext.add(i);
		res.addAll(allCombinaisons(nb, passedNext, n -1));
	}
	return res;
}

On peut choisir de travailler uniquement sur les indices des permutations et mapper ensuite nos objets.

🤔 Notre algorithme ici génère des doublons lorsque la source contient des doublons

Tester les combinaisons

Pour vérifier qu'une combinaison est valide, il faut vérifier:

  • même longueur de chaîne
  • que les lettres correspondent une à une
public static boolean match(List<String> a, List<String> b) {
	String la = a.stream().collect(Collectors.joining());
	String lb = b.stream().collect(Collectors.joining());
	if (la.length() != lb.length()) {
		return false;
	}
	for (int i = 0; i < la.length(); i++) {
		switch (la.charAt(i)) {
		case 'A':
			if (lb.charAt(i) != 'T') {
				return false;
			}
			break;
		case 'T':
			if (lb.charAt(i) != 'A') {
				return false;
			}
			break;
		case 'G':
			if (lb.charAt(i) != 'C') {
				return false;
			}
			break;
		case 'C':
			if (lb.charAt(i) != 'G') {
				return false;
			}
			break;
		}
	}
	return true;
}

💡 On peut aussi tester en remplaçant les lettres de la chaîne 2 par leur homologue, ne pas oublier de passer par un intermédiaire !

static String homologue(String e) {
	return e.replaceAll("A", "U").replaceAll("T", "A").replaceAll("U", "T")
			.replaceAll("G", "U").replaceAll("C", "G").replaceAll("U", "C");
}
Assembler les sous-chaînes

A partir d'une combinaison générée, il faut tester les N-2 découpages en deux possibles

List<String> combinaison;
for (int i = 1; i < n -1; i++) {
	List<String> brinGauche = new ArrayList<>();
	List<String> brinDroit = new ArrayList<>();
	for (int i0 = 0; i0 < i; i0++) {
		brinGauche.add(alls.get(combinaison.get(i0)));
	}
	for (int i1 = i; i1 < n; i1++) {
		brinDroit.add(alls.get(combinaison.get(i1)));
	}
}
ADN
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content