Analise de DNA Alienigena e Relatorio Cientifico sobre Mutacoes

O DNA DNA Depois de analisar cuidadosamente o disco voador que caiu no meio do parque da Redenção os cientistas chegaram a algumas conclusões sobre os seres que o ocupavam e que fugiram em uma cápsula de resgate Os cientistas descobriram que o DNA dos alienígenas é feito com 3 bases em vez das 4 bases do DNA terrestre Ironicamente eles batizaram as 3 bases de D N e A Eles também descobriram que o DNA alienígena sofre mutações que o deterioram com o tempo duas bases diferentes que estão uma ao lado da outra podem se fundir produzindo a terceira base e criando uma cadeia de DNA um pouco menor Isto acontece de uma forma muito organizada Em uma cadeia de DNA a fusão de bases acontece sempre na dupla de bases diferentes mais à esquerda A nova base criada com a fusão vai ser agregada ao final da cadeia de DNA Por exemplo a pequena cadeia DNA sofre uma deterioração em DN e acaba gerando AA Já uma cadeia maior como DNANDANDANDANADNDDDAN acaba virando simplesmente N Os cientistas agora perguntam dada uma cadeia de DNA qual o tamanho e qual cadeia podem ser obtidos depois de todas as mutações possíveis Você deve escrever um algoritmo capaz de ler as cadeias que os cientistas colocaram em vários arquivos de teste e depois informe o tamanho da menor cadeia que pode ser obtida em cada caso Ao final você deve apresentar um relatório descrevendo Qual o problema sendo resolvido Como o problema foi modelado Como é o processo de solução apresentando exemplos e algoritmos Os resultados dos casos de teste Conclusões ESTRUTURA DE DADOS Relatório Os cientistas descobriram que o DNA dos alienígenas é feito com 3 bases em vez das 4 bases do DNA terrestre Ironicamente eles batizaram as 3 bases de D N e A Eles também descobriram que o DNA alienígena sofre mutações que o deterioram com o tempo duas bases diferentes que estão uma ao lado da outra podem se fundir produzindo a terceira base e criando uma cadeia de DNA um pouco menor Isto acontece de uma forma muito organizada Em uma cadeia de DNA a fusão de bases acontece sempre na dupla de bases diferentes mais à esquerda A nova base criada com a fusão vai ser agregada ao nal da cadeia de DNA Diante deste cenário o objetivo deste trabalho é construir um algoritmo que consiga computar a mutação em uma cadeia de DNA Devido a mutação acontecer no meio da cadeia trocando duas bases por uma foi utilizado a estrutura de dados Lista Duplamente Encadeada Essa estrutura permite que em tempo constante O1 realizar a operação de fusão alterando a lista de DNA original A implementação foi realizada na linguagem Python a classe ListaDuplamenteEncadeada está descrita abaixo Classe No class No def initself valor selfvalor valor selfproximo None selfanterior None Classe Lista Duplamente Encadeada class ListaDuplamenteEncadeada def initself selfcabeca None selfcalda None def inserirself valor novono Novalor if not selfcabeca selfcabeca novono selfcalda novono return novonoanterior selfcalda selfcaldaproximo novono selfcalda novono def imprimirself atual selfcabeca while atual printatualvalor end atual atualproximo print Funcao auxiliar para retorna o resultado da fusao de duas bases def fusaoself valor1 valor2 conjunto D N A for elemento in conjunto if elemento valor1 and elemento valor2 return elemento def mutacaoself if selfcabeca None return atual selfcabeca whileatualproximo None ifatualvalor atualproximovalor atualvalor selffusaoatualvalor atualproximovalor atualproximo atualproximoproximo if atualproximo None atualproximoanterior atual if atualanterior None atual atualanterior else atual atualproximo O algoritmo contido na função mutacao consiste em percorrer a lista verificando se o elemento e o próximo são distintos se sim haverá uma fusão de bases e voltaremos caso exista a posição imediatamente anterior Caso as bases sejam iguais iremos apenas para a próxima posição da lista Para executar o código basta utilizar o seguinte comando no terminal linux python3 mainpy Abaixo consta os testes realizados da implementação da solução Podemos concluir que para cada problema computacional deve existir estruturas específicas que sejam mais eficientes de resolver o problema em questão No caso da lista duplamente encadeada nos permitiu resolver o problema com uma complexidade linear ESTRUTURA DE DADOS Relatório Os cientistas descobriram que o DNA dos alienígenas é feito com 3 bases em vez das 4 bases do DNA terrestre Ironicamente eles batizaram as 3 bases de D N e A Eles também descobriram que o DNA alienígena sofre mutações que o deterioram com o tempo duas bases diferentes que estão uma ao lado da outra podem se fundir produzindo a terceira base e criando uma cadeia de DNA um pouco menor Isto acontece de uma forma muito organizada Em uma cadeia de DNA a fusão de bases acontece sempre na dupla de bases diferentes mais à esquerda A nova base criada com a fusão vai ser agregada ao nal da cadeia de DNA Diante deste cenário o objetivo deste trabalho é construir um algoritmo que consiga computar a mutação em uma cadeia de DNA Devido a mutação acontecer no meio da cadeia trocando duas bases por uma foi utilizado a estrutura de dados Lista Duplamente Encadeada Essa estrutura permite que em tempo constante realizar a operação de 𝑂1 fusão alterando a lista de DNA original A implementação foi realizada na linguagem Python a classe ListaDuplamenteEncadeada está descrita abaixo Classe No class No def initself valor selfvalor valor selfproximo None selfanterior None Classe Lista Duplamente Encadeada class ListaDuplamenteEncadeada def initself selfcabeca None selfcalda None def inserirself valor novono Novalor if not selfcabeca selfcabeca novono selfcalda novono return novonoanterior selfcalda selfcaldaproximo novono selfcalda novono def imprimirself atual selfcabeca while atual printatualvalor end atual atualproximo print Funcao auxiliar para retorna o resultado da fusao de duas bases def fusaoself valor1 valor2 conjunto D N A for elemento in conjunto if elemento valor1 and elemento valor2 return elemento def mutacaoself if selfcabeca None return atual selfcabeca whileatualproximo None ifatualvalor atualproximovalor atualvalor selffusaoatualvalor atualproximovalor atualproximo atualproximoproximo if atualproximo None atualproximoanterior atual if atualanterior None atual atualanterior else atual atualproximo O algoritmo contido na função mutacao consiste em percorrer a lista verificando se o elemento e o próximo são distintos se sim haverá uma fusão de bases e voltaremos caso exista a posição imediatamente anterior Caso as bases sejam iguais iremos apenas para a próxima posição da lista Para executar o código basta utilizar o seguinte comando no terminal linux python3 mainpy Abaixo consta os testes realizados da implementação da solução Podemos concluir que para cada problema computacional deve existir estruturas específicas que sejam mais eficientes de resolver o problema em questão No caso da lista duplamente encadeada nos permitiu resolver o problema com uma complexidade linear