ILP Models for String Partition Considering Intergenic Regions and Indels
摘要
String partition problems have an important application in the development of algorithms for genome rearrangement distance problems. However, so far, the Integer Linear Programming approach has only been used for the simplest variation of string partition problems, where the representation of the genomes does not take the orientation of genes or intergenic regions into account, and the genomes must have the same set of genes. In this work, we propose Integer Linear Programming models for string partition problems incorporating information about gene orientation and intergenic regions, and allowing genomes with distinct gene sets. We also test the proposed models in simulated genomes.