Better ILP models for haplotype assembly.

BACKGROUND: The haplotype assembly problem for diploid is to find a pair of haplotypes from a given set of aligned Single Nucleotide Polymorphism (SNP) fragments (reads). It has many applications in association studies, drug design, and genetic research. Since this problem is computationally hard, both heuristic and exact algorithms have been designed for it. Although exact algorithms are much slower, they are still of great interest because they usually output significantly better solutions than heuristic algorithms in terms of popular measures such as the Minimum Error Correction (MEC) score, the number of switch errors, and the QAN50 score. Exact algorithms are also valuable because they can be used to witness how good a heuristic algorithm is. The best known exact algorithm is based on integer linear programming (ILP) and it is known that ILP can also be used to improve the output quality of every heuristic algorithm with a little decline in speed. Therefore, faster ILP models for the problem are highly demanded. RESULTS: As in previous studies, we consider not only the general case of the problem but also its all-heterozygous case where we assume that if a column of the input read matrix contains at least one 0 and one 1, then it corresponds to a heterozygous SNP site. For both cases, we design new ILP models for the haplotype assembly problem which aim at minimizing the MEC score. The new models are theoretically better because they contain significantly fewer constraints. More importantly, our experimental results show that for both simulated and real datasets, the new model for the all-heterozygous (respectively, general) case can usually be solved via CPLEX (an ILP solver) at least 5 times (respectively, twice) faster than the previous bests. Indeed, the running time can sometimes be 41 times better. CONCLUSIONS: This paper proposes a new ILP model for the haplotype assembly problem and its all-heterozygous case, respectively. Experiments with both real and simulated datasets show that the new models can be solved within much shorter time by CPLEX than the previous bests. We believe that the models can be used to improve heuristic algorithms as well.

An epidemiologic study of factors associated with nasal septum deviation by computed tomography scan: a cross sectional study.

BACKGROUND: Sinusitis is an inflammation of the paranasal sinuses that can be caused by anatomic variations of the nasal cavity and paranasal sinuses. In this study we aimed to find the relationship between sinusitis and septal deviation (SeD) and concha bullosa. METHODS: Two trained resident of ENT evaluated sinus CT scans of 463 cases presenting with nasal obstruction or chronic sinusitis symptoms from April 2011 to December 2011. CT scans were checked for the presence of conchae bullosa and the degree of septal deviation. The severity of sinusitis was evaluated according to the Lund Mackay criteria. The frequency of patients with different degrees of SeD and different grades of chronic sinusitis were studied. RESULTS: Of 463 cases, 47% had septal deviation. Concha bullosa was seen in 16.8% of the patients in the left side and 27.6% of them in the right side. There was no significant relationship between the presence of concha bullosa and the severity of sinusitis. Also the P value of analytical tests between the severity of sinusitis, osteomeatal involvement and the degree of septal deviation was not significant. Analysis of the relationship between the presence of SeD (either to right or left) and the severity of sinusitis in different sinuses revealed no significant P value. CONCLUSIONS: By this study, the relationship between concha bullosa in osteomeatal complex and the severity of sinusitis was not cleared. No relationship was found between the severity of sinusitis, osteomeatal involvement and the degree of septal deviation. Also SeD (either to right or left) was not found to be associated with the severity of sinusitis in different sinuses.