Your browser doesn't support javascript.
loading
Computing the family-free DCJ similarity.
Rubert, Diego P; Hoshino, Edna A; Braga, Marília D V; Stoye, Jens; Martinez, Fábio V.
Afiliação
  • Rubert DP; Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil.
  • Hoshino EA; Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil.
  • Braga MDV; Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.
  • Stoye J; Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.
  • Martinez FV; Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil. fhvm@facom.ufms.br.
BMC Bioinformatics ; 19(Suppl 6): 152, 2018 05 08.
Article em En | MEDLINE | ID: mdl-29745861
BACKGROUND: The genomic similarity is a large-scale measure for comparing two given genomes. In this work we study the (NP-hard) problem of computing the genomic similarity under the DCJ model in a setting that does not assume that the genes of the compared genomes are grouped into gene families. This problem is called family-free DCJ similarity. RESULTS: We propose an exact ILP algorithm to solve the family-free DCJ similarity problem, then we show its APX-hardness and present four combinatorial heuristics with computational experiments comparing their results to the ILP. CONCLUSIONS: We show that the family-free DCJ similarity can be computed in reasonable time, although for larger genomes it is necessary to resort to heuristics. This provides a basis for further studies on the applicability and model refinement of family-free whole genome similarity measures.
Assuntos
Palavras-chave
Texto completo
Adicionar na Minha BVS
Imprimir
XML
PubMed Links
Buscar no Google

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Assunto principal: Filogenia / Modelos Genéticos Limite: Animals / Humans Idioma: En Revista: BMC Bioinformatics Assunto da revista: INFORMATICA MEDICA Ano de publicação: 2018 Tipo de documento: Article País de afiliação: Brasil País de publicação: Reino Unido
Texto completo
Adicionar na Minha BVS
Imprimir
XML
PubMed Links
Buscar no Google

Texto completo: 1 Coleções: 01-internacional Base de dados: MEDLINE Assunto principal: Filogenia / Modelos Genéticos Limite: Animals / Humans Idioma: En Revista: BMC Bioinformatics Assunto da revista: INFORMATICA MEDICA Ano de publicação: 2018 Tipo de documento: Article País de afiliação: Brasil País de publicação: Reino Unido