@inproceedings{155d847231054364b2fed6f6b4e07138,
title = "Controlling size when aligning multiple genomic sequences with duplications",
abstract = "For a genomic region containing a tandem gene cluster, a proper set of alignments needs to align only orthologous segments, i.e., those separated by a speciation event. Otherwise, methods for finding regions under evolutionary selection will not perform properly. Conversely, the alignments should indicate every orthologous pair of genes or genomic segments. Attaining this goal in practice requires a technique for avoiding a combinatorial explosion in the number of local alignments. To better understand this process, we model it as a graph problem of finding a minimum cardinality set of cliques that contain all edges. We provide an upper bound for an important class of graphs (the problem is 7 NP-hard and very difficult to approximate in the general case), and use the bound and computer simulations to evaluate two heuristic solutions. An implementation of one of them is evaluated on mammalian sequences from the α-globin gene cluster.",
author = "Minmei Hou and Piotr Berman and Louxin Zhang and Webb Miller",
year = "2006",
doi = "10.1007/11851561_13",
language = "English (US)",
isbn = "3540395830",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "138--149",
booktitle = "Algorithms in Bioinformatics - 6th International Workshop, WABI 2006, Proceedings",
address = "Germany",
note = "6th International Workshop on Algorithms in Bioinformatics, WABI 2006 ; Conference date: 11-09-2006 Through 13-09-2006",
}