title: Genomic distance under gene substitutions.
abstract: BACKGROUND
  The distance between two genomes is often computed by comparing only the common markers between them. Some approaches are also able to deal with non-common markers, allowing the insertion or the deletion of such markers. In these models, a deletion and a subsequent insertion that occur at the same position of the genome count for two sorting steps.
  
  
  RESULTS
  Here we propose a new model that sorts non-common markers with substitutions, which are more powerful operations that comprehend insertions and deletions. A deletion and an insertion that occur at the same position of the genome can be modeled as a substitution, counting for a single sorting step.
  
  
  CONCLUSIONS
  Comparing genomes with unequal content, but without duplicated markers, we give a linear time algorithm to compute the genomic distance considering substitutions and double-cut-and-join (DCJ) operations. This model provides a parsimonious genomic distance to handle genomes free of duplicated markers, that is in practice a lower bound to the real genomic distances. The method could also be used to refine orthology assignments, since in some cases a substitution could actually correspond to an unannotated orthology.
authors.affiliation: Instituto Nacional de Metrologia, Qualidade e Tecnologia, Duque de Caxias, 25250-020, Brazil. mdbraga@inmetro.gov.br
authors.forename: Marília D V
authors.initials: MD
authors.lastname: Braga
authors.forename: Raphael
authors.initials: R
authors.lastname: Machado
authors.forename: Leonardo C
authors.initials: LC
authors.lastname: Ribeiro
authors.forename: Jens
authors.initials: J
authors.lastname: Stoye
mesh_terms: D000465:Algorithms; D005819:Genetic Markers; D016678:Genome; D023281:Genomics / Q000379:methods*; D006801:Humans; D054643:INDEL Mutation; D008957:Models, Genetic
chemical_list: D005819:Genetic Markers